动态规划初步
No.1 (最长递增子序列)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | #include <bits/stdc++.h> using namespace std; int dp[50020]; int main() { int N,a[50020]; cin>>N; for(int i=0;i<N;i++) cin>>a[i]; dp[0]=1; for(int i=1;i<N;i++) { dp[i]=1; for(int j=0;j<i;j++) { if(a[i]>a[j]) dp[i]=max(dp[j]+1,dp[i]); } } int maxx=-0x3f; for(int i=1;i<N;i++) { if(dp[i]>maxx)maxx=dp[i]; } cout<<maxx<<endl; return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | #include <iostream> #include <cstring> #include <cmath> using namespace std; string a,b,t; int dp[1020][1020]; int main() { cin>>a>>b; int n=a.length(); int m=b.length(); memset(dp,0,sizeof(dp)); for(int i=0;i<=max(n,m);i++) dp[0][i]=dp[i][0]=i; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]; else dp[i][j]=dp[i-1][j-1]+1; dp[i][j]=min(min(dp[i-1][j],dp[i][j-1])+1,dp[i][j]); } } cout<<dp[n][m]<<endl; return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | #include <bits/stdc++.h> using namespace std; int LCS[1020][1020],mark[1020][1020]; string s1,s2,s,ans; void output(int x,int y) { if(x<=0||y<=0)return; else if(mark[x][y]==1) { output(x-1,y-1); cout<<s1[x-1]; } else if(mark[x][y]==-1) output(x-1,y); else output(x,y-1); } int main() { cin>>s1>>s2; for(int i=0;i<=s1.length();i++) { for(int j=0;j<=s2.length();j++) { if(i==0) { LCS[i][j]=0; mark[i][j]=-1; } else if(j==0) { LCS[i][j]=0; mark[i][j]=0; } else if(s1[i-1]==s2[j-1]) { LCS[i][j]=LCS[i-1][j-1]+1; mark[i][j]=1; } else { if(LCS[i-1][j]>LCS[i][j-1]) { LCS[i][j]=LCS[i-1][j]; mark[i][j]=-1; } else { LCS[i][j]=LCS[i][j-1]; mark[i][j]=0; } } } } output(s1.length(),s2.length()); cout<<endl; return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #include<bits/stdc++.h> typedef long long ll; using namespace std; ll sum,a[520][520],dp[520]; ll N,M,mas=-1,temp; ll maxsub() { ll mas=0,t=0; for(int i=0;i<M;i++) { if(t>0)t+=dp[i]; else t=dp[i]; if(t>mas)mas=t; } return mas; } int main() { cin>>M>>N; for(int i=0;i<N;i++) for(int j=0;j<M;j++) cin>>a[i][j]; for(int i=0;i<N;i++) { memset(dp,0,sizeof(dp)); for(int j=i;j<N;j++) { for(int k=0;k<M;k++) dp[k]+=a[j][k]; temp=maxsub(); if(temp>mas)mas=temp; } } if(mas>=0)cout<<mas<<endl; else cout<<0<<endl; return 0; } |