————dp非常灵活,对像我这样的蒟蒻及其不友好。写此小结记录下自己成长的过程
首先呢,拿到一个题怎么发现他是由dp来解决的呢?有以下几点:
1.可以由一个子问题推出一个全局最优解
2.无后效性
而做dp的题无非就三部曲
1.确认子问题及其边界
2.推出状态转移方程
3.进行动态规划编程
线性dp:
线性dp过于灵活,不像区间dp以及背包问题那样有模板,就我目前你遇到的线性dp来做个总结
首先呢就是LIS
例题一:http://120.78.128.11/Problem.jsp?pid=1388
给定一个序列求最长上升子序列。我觉得这是一个最最基础的dp题了。
首先就是确认子状态了:假设dp[i]是序列第i个数的最长子序列的长度,那么这个dp[i]就是由在i之前的比a[i]小的数的最大dp[i]+1,于是乎我们就可以推出状态方程dp[i]=max(满足a[i]>=a[j]的dp[j])+1。接下来就是写代码了
#include<stdio.h> #include<iostream> using namespace std; int a[1001]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); int maxlen[1001]={0}; for(int i=2;i<=n;i++) for(int j=1;j<i;j++)if(a[i]>a[j])maxlen[i]=max(maxlen[i],maxlen[j]+1); int maix=-1; for(int i=1;i<=n;i++)maix=max(maix,maxlen[i]); printf("%d",maix+1); }
最长下降子序列的过程也和这个差不多
例题二:http://120.78.128.11/Problem.jsp?pid=2399
这题可以把它看成一个最长上升子序列加最长下降子序列,只需要枚举出在哪一个点转折就好了
#include<bits/stdc++.h> using namespace std; int dp[105][105]={0}; int T[105]; int main() { int n,ans=0; cin>>n; for(int i=1;i<=n;i++)cin>>T[i]; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++) for(int k=i;k>=j+1;k--) if(T[k]>T[j])dp[i][k]=max(dp[i][k],dp[i][j]+1); for(int j=i;j<=n;j++) for(int k=n;k>=j+1;k--) if(T[k]<T[j])dp[i][k]=max(dp[i][k],dp[i][j]+1); for(int j=1;j<=n;j++)ans=max(ans,dp[i][j]); } cout<<n-ans-1<<endl; return 0; }
例题三:http://120.78.128.11/Problem.jsp?pid=2125
这题和例题一差不多,只不过将a[i]>a[j]这个条成:要赢一个对手,你不仅要在题数上碾压他,还要做出所有对手做出的题目。由题目的意思来说,只要排名靠后的人的a[i]&a[j]==a[j]就是赢得比赛,所以我们只需要枚举第i个人排名前面的所有人,并找到符合条件的最大分数+1即可,转移方程就可得:dp[j]=max(dp[j],dp[i]+1);
代码如下:
#include<stdio.h> int a[10001]={0}; int dp[10001]={0}; int main() { int n; while(~scanf("%d",&n)) { if(n==0) { printf("0\n"); continue; } int ans=0; for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { int asd=a[i]&a[j]; if(asd==a[i]) { dp[j]=dp[j]>dp[i]+1?dp[j]:dp[i]+1; ans=ans>dp[j]?ans:dp[j]; } } dp[i]=0; } printf("%d\n",ans); } return 0; }
例题四:http://120.78.128.11/ProblemInfo.jsp?pid=2297
这题是由前一个状态,选择用筷子还是勺子,由欠你一个状态来转移
#include<bits/stdc++.h> using namespace std; long long a[200],b[200],c[200]; long long dp[200][2]; int main() { int n; while(cin>>n){ for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i]; memset(dp,0x3f3f,sizeof(dp)); dp[0][1]=0; for(int i=1;i<=n;i++){ dp[i][0]=min(dp[i-1][0],dp[i-1][1]+c[i])+a[i]; if(i!=1)dp[i][1]=min(dp[i-1][0]+c[i],dp[i-1][1])+b[i]; else dp[i][1]=b[i]; } printf("%lld\n",min(dp[n][0],dp[n][1])); } return 0; }
线性dp还有一个很典型的例题:http://120.78.128.11/Problem.jsp?pid=1386
用i表示第一个串的下标,用j表示第二个串的下标如果a[i]==b[j]就等于前a的前i-1个和b的前j-1个之中的最长公共子串
#include<iostream> using namespace std; int maxlen[1001][1001]={0}; int main() { string a,b; while(cin>>a>>b) { maxlen[0][0]=0; for(int i=1;i<=a.length();i++) { for(int j=1;j<=b.length();j++) { if(a[i-1]==b[j-1]) { maxlen[i][j]=maxlen[i-1][j-1]+1; } else { maxlen[i][j]=max(maxlen[i-1][j],maxlen[i][j-1]); } } } cout<<maxlen[a.length()][b.length()]<<endl; } return 0; }