T1 采药
太典了。
大家闭着眼睛都能敲出来。(?)
#include <iostream> using namespace std; int T,M; int t[1005],v[1005],dp[1005]; int main(){ cin>>T>>M; for(int i=1;i<=M;i++){ cin>>t[i]>>v[i]; } for(int i=1;i<=M;i++){ for(int p=T;p>=1;p--){ if(p>=t[i]){ dp[p]=max(dp[p],dp[p-t[i]]+v[i]); } } } cout<<dp[T]; }
T2 最长上升子序列
题目:
逆向防御导弹?)
#include <iostream> using namespace std; const int N=1e6+5; int n; int num[5005]; int dp[5005]; int ans=1; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>num[i]; for(int j=i-1;j>=1;j--){ if(num[j]<num[i]&&dp[i]<dp[j]+1){ dp[i]=dp[j]+1; } } if(dp[i]==0) dp[i]=1; if(dp[i]>ans) ans=dp[i]; } cout<<ans; return 0; }
T3 最大序列和
题目:
更新的式子同样很好找到。
要注意的只是判断的条件而已。
#include <iostream> using namespace std; int n,ans=-999999; int num[200005],dp[200005]; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>num[i]; dp[i]=num[i]; if(i!=1&&dp[i-1]>=0){ dp[i]=dp[i]+dp[i-1]; } if(dp[i]>ans) ans=dp[i]; } cout<<ans; return 0; }
T4 LCS
太典了,啧啧啧。
也是大家闭着眼睛也能敲出来的东西(?)
#include <bits/stdc++.h> using namespace std; int dp[3005][3005]; int max_,a1,b1; string ans; int main(){ string a,b; getline(cin,a); getline(cin,b); int len1=a.length(); int len2=b.length(); //矩阵边边要从0开始,下标0为dp中的1. for(int i=0;i<len1;i++){ for(int l=0;l<len2;l++){ if(a[i]==b[l]) dp[i+1][l+1]=dp[i][l]+1; else dp[i+1][l+1]=max(dp[i][l+1],dp[i+1][l]); if(dp[i+1][l+1]>max_){ max_=dp[i+1][l+1]; a1=i+1; b1=l+1; } } } while(a1>0&&b1>0){ if(a[a1-1]==b[b1-1]){ ans=a[a1-1]+ans; a1-=1; b1-=1; } else{ if(dp[a1-1][b1]>dp[a1][b1-1]) a1-=1; else b1-=1; } } cout<<ans; }