admin 管理员组

文章数量: 893893

第五章 动态规划法(必做题)

最长公共子序列

设第一个串为X,第二个串为Ydp[i][j]表示X中前i个字符与Y中前j个字符中最大的公共子序列长度。dp[i][j]只能从dp[i-1][j]dp[i][j-1]dp[i-1][j-1]中转移得到。

如果X[i]==Y[i],则dp[i][j]=max(dp[i-1][j-1]+1, dp[i][j-1], dp[i-1][j])(其实后面两项可以去掉,因为它们至多比dp[i-1][j-1]大1,即小于等于dp[i-1][j-1]+1),即dp[i][j]=dp[i-1][j-1]+1

如果X[i]!=Y[j],则dp[i][j]=max(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])(同理,第一项可以去掉,即dp[i][j]=max(dp[i][j-1], dp[i-1][j])。

#include<bits/stdc++.h>
using namespace std;const int maxn = 1000 + 3; //+3防止出现一些不可描述的问题
char X[maxn], Y[maxn];
int dp[maxn][maxn];
int main(int argc, char const *argv[])
{cin >> (X + 1) >> (Y + 1); //从第2个位置存起int lx = strlen(X + 1);int ly = strlen(Y + 1);dp[lx][ly]=0;for (int i = 1; i <= lx; i++) {for (int j = 1; j <= ly; j++) {if (X[i] == Y[j]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}cout << dp[lx][ly] << endl;return 0;
}

最大价值

 完全背包,见这个链接

#include<bits/stdc++.h>
using namespace std;const int maxn = 100+3;
int dp[maxn*maxn];
int v[maxn];
int w[maxn];int main(){int V;cin>>V;int N;cin>>N;for(int i=1;i<=N;i++){cin>>v[i]>>w[i];}for(int i=1;i<=N;i++){for(int j=v[i];j<=V;j++){dp[j] = max(dp[j], dp[j-v[i]]+w[i]);}}cout<<dp[V]<<endl;return 0;
}

 若每个物品只有一件,则01背包

背包总的容量为V,设dp[i][j]为前i个物品,消耗容量j所能得到的最大价值。

第i个物品,价值为vi,体积为wi,所以如果放第i个物品,则需要消耗wi的容量,即前i-1个物品最多消耗的容量,即dp[i][j]=max(dp[i-1][j-wi]+vi, dp[i-1][j])

路数

假设卒走到点,那么它只能是从 或走到

设dp[i][j]是从走到的种类数,由上分析有,dp[i][j]=dp[i-1][j]+dp[i][j-1],这里需要注意边界,不是每一个点都有两个上一个点的。然后需要判断一下,当前点是不是在马的范围内。

#include<bits/stdc++.h>
using namespace std;const int maxn = 1000+3;
typedef long long ll;
ll dp[maxn][maxn];// judge the horse range
bool check(int i, int j, int Bx, int By){if(i==Bx&&j==By) return true;if((i==Bx-1||i==Bx+1) && (j==By-2||j==By+2)) return true;if((i==Bx-2||i==Bx+2) && (j==By-1||j==By+1)) return true;return false;
}
int main(){int Ax, Ay, Bx, By;cin>>Ax>>Ay>>Bx>>By;dp[0][0]=1;for(int i=0;i<=Ax;i++){for(int j=0;j<=Ay;j++){if(i-1>=0 && check(i,j,Bx,By)==false) dp[i][j] += dp[i-1][j];if(j-1>=0 && check(i,j,Bx,By)==false) dp[i][j] += dp[i][j-1];// cout<<i<<" "<<j<<" "<<check(i,j,Bx,By)<<endl;// cout<<dp[i][j]<<" ";}// cout<<"\n";}cout<<dp[Ax][Ay]<<endl;return 0;
}

递增子序列

 假设dp[i][j],是以结尾的,长度为j的,递增的,子序列的个数(有点点绕。。),则特别地,dp[i][1]=1。

#include<bits/stdc++.h>
using namespace std;const int maxn = 1000+3;
typedef long long ll;
ll dp[maxn][maxn];int a[maxn];
int main(){int n,k;cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}ll ans=0;for(int i=1;i<=n;i++){dp[i][1]=1;for(int j=1;j<=min(k,i);j++){for(int ii=1;ii<=i;ii++){if(a[i]>a[ii]){dp[i][j]+=dp[ii][j-1];}}}ans+=dp[i][k];}cout<<ans<<endl;return 0;
}

本文标签: 第五章 动态规划法(必做题)