算法 c++ 备战蓝桥杯---动态规划（基础2）

本专题主要是介绍几个比较经典的题目：

假设我们令f[i]为前i个的最长不下降子序列，我们会发现难以转移方程很难写（因为我们不知道最后一个数）。

于是，我们令f[i]为以i结尾的最长不下降子序列，这样子我们就可以得出

f[i]=max{f[j]+1}(a[j]<=a[i]&&j

f[i]=1;

复杂度为n^2;用单调队列维护可nlogn;

下面给出用递归for循环代码：

#include

using namespace std;

int n,a[100000],dp[100000];

deque q;

int main(){

cin>>n;

for(int i=1;i<=n;i++) scanf("%d",&a[i]);

dp[1]=1;

for(int i=2;i<=n;i++){

for(int j=1;j

if(a[j]<=a[i]) dp[i]=max(dp[i],dp[j]+1);

}

}

int ans=0;

for(int i=1;i<=n;i++) ans=max(ans,dp[i]);

cout<

}

下面是用记忆化搜索实现：

#include

using namespace std;

int n,a[100000],dp[100000];

deque q;

int f(int x){

if(dp[x]!=0) return dp[x];

for(int i=1;i<=x-1;i++){

if(a[i]<=a[x]) dp[x]=max(dp[x],f(i)+1);

}

return dp[x];

}

int main(){

cin>>n;

int ans=0;

for(int i=1;i<=n;i++) scanf("%d",&a[i]);

dp[1]=1;

for(int i=1;i<=n;i++){

ans=max(ans,f(i));

}

cout<

}

接题：

我们设f[i][j]表示从i,j滑下的最长路径，易得：

f[i][j]=max{f[i-1][j]+1,f[i+1][j]+1,f[i][j+1]+1,f[i][j-1]+1}(a[i-1][j]

在实现上，for循环不知道某先f[i][j]，我们需要按从低到高的顺序求，比较麻烦。

于是我们用记忆化搜索。

下面是AC代码：

#include

#include

#include

#include

using namespace std;

#define int long long

int a[105][105],r,c,ans,dp[105][105];

int f(int i,int j){

if(i<=0||j<=0||i>r||j>c) return 0;

if(dp[i][j]!=0) return dp[i][j];

if(a[i-1][j]

if(a[i+1][j]

if(a[i][j-1]

if(a[i][j+1]

if(dp[i][j]==0) return dp[i][j]=1;

else return dp[i][j];

}

signed main(){

cin>>r>>c;

for(int i=1;i<=r;i++){

for(int j=1;j<=c;j++){

scanf("%d",&a[i][j]);

}

}

for(int i=1;i<=r;i++){

for(int j=1;j<=r;j++){

ans=max(ans,f(i,j));

}

}

cout<

}

精彩文章