考前抱佛脚系列
动态规划常见模版
1 最大子段和
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 0x7fffffff;
int num[101];
int main() {int N;cin>>N;for(int i=0;i<N;i++){cin>>num[i];}int ans=-inf;for(int i=0;i<N;i++){ans=max(ans,num[i]);}if(ans<=0){cout<<ans<<endl;}else{int sum=0;for(int i=0;i<N;i++){if(sum+num[i]<0){sum=0;}else{sum+=num[i];}ans=max(ans,sum);}cout<<ans<<endl;}return 0;
}
2 最长上升子序列(LIS)
#include <iostream>
#include <cstring>
using namespace std;
int dp[101],a[101],n;
int LIS(){int ans=0;for(int i=1;i<=n;i++){dp[i]=1;for(int j=1;j<i;j++){if(a[j]<a[i]){dp[i]=max(dp[i],dp[j]+1);}}ans=max(ans,dp[i]);}return ans;
}
int main() {cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}cout<<LIS()<<endl;return 0;
}
3 最长公共子序列(LCS)
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int dp[110][110];
int main() {string a,b;memset(dp,0,sizeof(dp));cin>>a>>b;int lena=a.size();int lenb=b.size();for(int i=1;i<=lena;i++){for(int j=1;j<=lenb;j++){if(a[i-1]==b[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}}cout<<dp[lena][lenb]<<endl;return 0;
}