首页 > 代码库 > 最近做的DP类题的总结~
最近做的DP类题的总结~
感觉自己DP确实太弱。。。
Codeforces Round #156 (Div. 1) A. Almost Arithmetical Progression
题意:在保持循序的情况下，从一个数组取出最多的数，这些数是交替出现的，例如，1,2,1,2，、。。
dp[i][j] 表示前i 个数，第 j 个数和第 i 个数被取出可以组成最长序列
我们用pre[i]记录 i 上一次出现的位置，这样就可以好好转移了。。。
#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define mod 1000000007#define maxn 1000010#define pi acos(-1.0)#define eps 1e-6using namespace std;int dp[4001][4001],a[4010],pre[maxn];int num[maxn] ;int main(){ int i,m,n,k,j ; int id,ans; while(scanf("%d",&n) != EOF) { for( i = 1 ; i <= n ;i++) scanf("%d",&a[i]) ; memset(pre,-1,sizeof(pre)) ; memset(num,0,sizeof(num)) ; ans=1; for(i = 1 ; i <= n ;i++) { id=pre[a[i]]; num[a[i]]++; ans=max(num[a[i]],ans); pre[a[i]] = i ; for( j = 1 ; j < i ;j++) { if(id==-1)dp[j][i]=2 ; else if(j>id)dp[j][i] = 1+dp[id][j]; else if(j<id)dp[j][i] = dp[j][id]; ans=max(ans,dp[j][i]) ; } } cout <<ans<<endl; } return 0 ;}/256/problem/A
poj 1141 Brackets Sequence
题意: 给你一个字符串，你可以任意插入字符，使得塔变成回文串，长度要求最小，
然后把这个回文串输出来
dp[i][j]表示把 i-j变成回文串后的最短长度；
pre[x][y][2] 表示x,y从哪里转移过来的
然后 从 1,n经行 dfs，把需要增加字符和它匹配的位置标记
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define mod 1000000007#define maxn 210#define pi acos(-1.0)#define eps 1e-6#define INF 0x3f3f3f3fusing namespace std;int dp[maxn][maxn],pre[maxn][maxn][2] ;char a[maxn];bool vi[maxn] ;bool check(char a,char b){ if(a==‘(‘&&b==‘)‘) return true; if(a==‘[‘&&b==‘]‘) return true; return false;}void out(char a){ if(a==‘(‘||a==‘)‘)printf("()") ; else printf("[]");}void dfs(int x,int y ){ if(x>y) return ; if(x>=y){vi[x]=true ;return;} int xx = pre[x][y][0],yy=pre[x][y][1] ; // cout << xx<<"--" <<yy<<endl; // cout<<x<<" "<<y<<endl; if(xx==x&&yy+1==y) { vi[y] = true; dfs(xx,yy) ; } else if(xx-1==x&&yy==y) { vi[x] = true; dfs(xx,yy); } else if(xx-1==x&&yy+1==y) { if(yy==xx)vi[xx]=1; dfs(xx,yy); } else { dfs(xx,yy) ; dfs(yy+1,y) ; }}int main(){ int cnt1,cnt2,n,i; int j , k , T,m ; while(gets(a+1) > 0 ) { n = strlen(a+1) ; memset(dp,0,sizeof(dp)); memset(vi,0,sizeof(vi)); for( i = 1 ; i <= n ;i++) { dp[i][i]=2; for( j =i-1 ; j >= 1 ;j--) { dp[j][i] = dp[j][i-1]+2 ; pre[j][i][0]=j; pre[j][i][1]=i-1; if(dp[j+1][i]+2 < dp[j][i]){ dp[j][i] = dp[j+1][i]+2; pre[j][i][0]=j+1; pre[j][i][1]=i; } for( k = j+1 ; k < i ;k++) { if(dp[j][k]+dp[k+1][i] < dp[j][i]) { dp[j][i] = dp[j][k]+dp[k+1][i] ; pre[j][i][0]=j; pre[j][i][1]=k; } } if(check(a[j],a[i])&& 2+dp[j+1][i-1] < dp[j][i]) { dp[j][i] = dp[j+1][i-1]+2; pre[j][i][0]=j+1; pre[j][i][1]=i-1; } } } dfs(1,n); for( i = 1 ; i <= n ;i++) { if(vi[i])out(a[i]) ; else printf("%c",a[i]); } puts("") ; } return 0 ;}
poj 3280 Cheapest Palindrome
题意：每个字符都有删除它的代价增加它的代价,问最小的代价使得给出的字符串变成回文串
dp[i][j]表示，i-j变成字符串的最小代价
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define mod 1000000007#define maxn 2010#define pi acos(-1.0)#define eps 1e-6using namespace std;int dp[maxn][maxn];char a[maxn] ;int cost1[210] ,cost2[210];int main(){ int cnt1,cnt2,n,i; int j , k , T,m ; char s[5] ; while(scanf("%d%d",&n,&m) != EOF) { scanf("%s",a+1) ; for( i = 1 ; i <= n ;i++) { scanf("%s",s) ; scanf("%d%d",&cost1[s[0]],&cost2[s[0]]) ; } memset(dp,0x3f3f3f,sizeof(dp)) ; for( i = 1 ; i <= m;i++) { dp[i][i]=0; for( j = i-1 ; j >= 1 ;j--) { dp[j][i] = dp[j][i-1]+min(cost1[a[i]],cost2[a[i]]) ; dp[j][i] = min(dp[j][i],dp[j+1][i]+min(cost1[a[j]],cost2[a[j]])) ; // cout <<j <<" " << i << " "<<dp[j][i] << endl; if(a[i]==a[j]) { dp[j][i] = min(dp[j][i],dp[j+1][i-1]) ; if(i==j+1)dp[j][i]=0; } } } cout <<dp[1][m] << endl; } return 0 ;}
poj 2955 Brackets
题意:给出一个字符串，按先后循序不变选出一些字符组成一个回文串，要求这个回文串最长
dp[i][j]表示i-j可以选出最长的回文串
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define mod 1000000007#define maxn 110#define pi acos(-1.0)#define eps 1e-6using namespace std;int dp[maxn][maxn];char a[maxn] ;bool check(char a,char b){ if(a==‘(‘&&b==‘)‘) return true; if(a==‘[‘&&b==‘]‘) return true; return false;}int main(){ int cnt1,cnt2,n,i; int j , k , T ; while(scanf("%s",a+1) != EOF) { if(a[1]==‘e‘) break ; n = strlen(a+1) ; memset(dp,0,sizeof(dp)) ; for( j = 1 ; j <= n ;j++) { for( i = j-1; i >= 1 ;i--) { dp[i][j] = 0; if(check(a[i],a[j])) dp[i][j] = max(dp[i][j],dp[i+1][j-1]+1) ; for(k = i ; k < j ; k++) dp[i][j] = max(dp[i][k]+dp[k+1][j],dp[i][j]); } } cout << dp[1][n]*2 << endl; } return 0 ;}
hdu 2476 String painter
题意:每个你可以把a的一段居间刷成任意的一个字符，求把a变成 b 需要的最少刷的次数
dp[i][j] 表示把空串(相当于任意串)变成 b 中 i-j 子串的最小刷次数，
dp[i][j] = 1+dp[i+1][j] ;
如果 b[k]==b[i] ( k > i && k <= j ) 那么 b[i] 和 b[k] 可以一起刷出来 ，
dp[i][j] = min(dp[i][j],dp[i+1][k]+dp[k+1][j]) ;
然后 a和b 的匹配， ans[i]表示把 1-i变成相同最小的改变次数
如果 a[i]==b[i] 那么ans[i]=ans[i-1]；
不然，就去枚举 1-i
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define mod 1000000007#define maxn 210#define pi acos(-1.0)#define eps 1e-6#define INF 0x3f3f3f3fusing namespace std;int dp[maxn][maxn],ans[maxn] ;char a[maxn],b[maxn] ;int main(){ int cnt1,cnt2,n,i; int j , k , T,m ; while(scanf("%s%s",a+1,b+1) != EOF) { n = strlen(a+1) ; memset(dp,0,sizeof(dp)) ; for( i = 1 ; i <= n ;i++) { dp[i][i]=1; for( j = i-1 ; j >= 1 ;j--) { dp[j][i] = 1+dp[j+1][i]; for( k = j+1 ; k <= i ;k++)if(b[j]==b[k]) dp[j][i] = min(dp[j][i],dp[j+1][k]+dp[k+1][i]) ; // cout << j <<" " <<i<<" "<<dp[j][i]<<endl; } } ans[0]=0; for( i= 1 ; i <= n ;i++) { if(a[i]==b[i])ans[i]=ans[i-1] ; else { ans[i]=ans[i-1]+1; for( j = i ; j >= 1 ;j--) ans[i]=min(ans[i],ans[j-1]+dp[j][i]) ; } } cout <<ans[n]<<endl; } return 0 ;}
poj 3661 Running
题意:给出某个人n 分钟内每分钟可以跑步的距离，跑一分钟疲劳增加1 ，疲劳度不能超过 m ，
他某个时候可以选择休息，休息一分钟可以疲劳度减1,不过等到疲劳度为 0 才可以继续跑步
在 第n 分钟结束时，他的疲劳度必须为 0 ,问最长可以跑多远
dp[i][j] 表示，第i 分钟，疲劳度为 j 时最远可以跑多远
如果选择跑步 dp[i][j] = dp[i-1][j-1]+a[i]
不过 dp[i-1][j]不能转移到它，因为必须休息到0才能跑，
如果转移了，那么下一次用到它的转移就会出错。
dp[i][0] = dp[i-1][0] ;
或者第 j 分钟 选择休息 dp[i][0] = max(dp[i][0],dp[j][i-j]) ;
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define mod 1000000007#define maxn 10010#define pi acos(-1.0)#define eps 1e-6#define INF 0x3f3f3f3fusing namespace std;int dp[10001][510];int a[maxn];int main(){ int cnt1,cnt2,n,i; int j , k , T,m ; while(scanf("%d%d",&n,&m) != EOF) { for( i = 1 ; i <= n ;i++) scanf("%d",&a[i]) ; memset(dp,0,sizeof(dp)) ; for( i = 1 ; i <= n ;i++) { for( j = 1 ; j <= m ;j++) { dp[i][j]=dp[i-1][j-1]+a[i]; } dp[i][0]=max(dp[i-1][0],dp[i-1][1]) ; for(int k=1;k<=m;k++)if(i-k>=0) dp[i][0]=max(dp[i][0],dp[i-k][k]); } cout << dp[n][0] << endl; } return 0 ;}
最近做的DP类题的总结~
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。