天梯赛DP汇总

天梯赛DP出的貌似比较少，在前面的题中（L1,L2,L3中的1，2题）涉及到的有一定思维量但是也不是特别难，仔细想想还是可以做的

1.记忆化搜索：PTA | 程序设计类实验辅助教学平台

AC代码：

#include<bits/stdc++.h>
using namespace std;
string c;
int dp[1010][1010],n;
int maxx=1;
void dfs(int l,int r){if(l>n||r<0) return;if(dp[l][r]!=-1) return;if(l>r){dp[l][r]=0;return;}if(c[l]!=c[r]){dp[l][r]=0;return;}else{if(r==l+1){dp[l][r]=1;return;}else{dfs(l+1,r-1);dp[l][r]=dp[l+1][r-1];return;}}
}
int main(){getline(cin,c);n=c.size();c=" "+c;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){dp[i][j]=-1;}}for(int i=1;i<=n;i++) dp[i][i]=1;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){if(dp[i][j]==-1) dfs(i,j);if(dp[i][j]==1){maxx=max(j-i+1,maxx);}  }}    cout<<maxx;
}

2.DP+路径：PTA | 程序设计类实验辅助教学平台

不考虑字典序的话就是一个背包问题，如何让字典序min，一开始我是从小到大排，但是这个贪心是存在问题的，正解应该是从大到小再反序输出，这样就可以发挥字符串前面字符的决定性作用，满足要求，AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[200100];
int dp[10100][110];//记录前一个，没有就是-1,首个为0
int ans[100010],cnt;
map<int,int> mp;
void dfs(int w,int kk){if(w==0) return;ans[++cnt]=a[dp[kk][w]];int ci=dp[kk][w]-1;w-=a[dp[kk][w]];if(w==0) return;dfs(w,ci);
}
bool cmp(int a,int b){return a>b;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){if(mp[a[i]]==0) mp[a[i]]=i;else continue;}for(int i=0;i<=n;i++){for(int j=0;j<=m;j++){dp[i][j]=-1;}}dp[0][0]=0;dp[1][0]=0;dp[1][a[1]]=1;for(int i=2;i<=n;i++){for(int j=0;j<=m;j++) dp[i][j]=dp[i-1][j];for(int j=a[i];j<=m;j++){if(dp[i-1][j-a[i]]>=0){dp[i][j]=i;}}}if(dp[n][m]==-1){cout<<"No Solution";}else{dfs(m,n);for(int i=1;i<=cnt;i++){if(i==cnt) cout<<ans[i];else{cout<<ans[i]<<" ";}}}
}

3.DP：PTA | 程序设计类实验辅助教学平台

这个很容易想到用dp[i][j]表示前i个子串删j个字符的种类数

dp[i][j]=dp[i-1][j]+dp[i-1][j-1]-删去的个数

如何计算删去多少？

从后枚举最多k个，如果与最后一个元素相等，就一定会重，减去相应的dp即可，见AC代码：

#include<bits/stdc++.h>
using namespace std;
string s;
long long sum=0;
long long dp[2000100][4],n;
int main(){cin>>s;n=s.size();s=" "+s;dp[0][0]=1;for(int i=1;i<=n;i++){for(int k=0;k<=3;k++){if(k==0) dp[i][k]=1;else dp[i][k]=dp[i-1][k]+dp[i-1][k-1];if(i==k){dp[i][i]=1;continue;}//减去重的for(int j=i-1;j>=max(i-k,1);j--){if(s[i]==s[j]){dp[i][k]-=dp[j-1][k-(i-j)];break;}}}}for(int i=0;i<=3;i++) sum+=dp[n][i];cout<<sum<<endl;//cout<<dp[1][2];
}

4.树型DP：PTA | 程序设计类实验辅助教学平台

感觉可能是PTA中DP中最好的一道题了，类似上司的舞会。

注意一个小trick：每一个子树只有-1，0，1这三个属性，因此当有的子树节点+自己为偶数时，把他们整体看成一个整体的子树只能是0，反之为+1或-1，因此我们令dp[i][j]表示以i为子树值为j的最小价格，这样我们枚举它的子树是对于偶数的直接跳过，对于奇数的就按照上司舞会的那个trick来即可

#include<bits/stdc++.h>
using namespace std;
int n;
int rd[200010],root;
int cost[200010],sum[200010];
int color[200010];
int dp[200010][4];//dp[i][j]表示第i个子树是完美树并且整个值为j(-1白,0黑,1无)的最小代价
vector<int> edge[200100];
void dfs(int x, int fa){int cnt=0;for(int i=0;i<edge[x].size();i++){if(edge[x][i]==fa) continue;cnt++;}if(!cnt){dp[x][color[x]]=0;dp[x][1-color[x]]=cost[x];dp[x][2]=1e9;return;}vector<pair<int,int> > v;int cc=0;int yyy=1;for(int i=0;i<edge[x].size();i++){if(edge[x][i]==fa) continue;dfs(edge[x][i],x);if(sum[edge[x][i]]%2==0) cc+=dp[edge[x][i]][2];else{yyy++;cc+=dp[edge[x][i]][1];v.push_back({dp[edge[x][i]][0]-dp[edge[x][i]][1],edge[x][i]});}}if(!color[x]){cc+=cost[x];v.push_back({-cost[x],x});}else v.push_back({cost[x],x});sort(v.begin(),v.end());//cout<<v[0].first<<endl;//还是按照原来的颜色//对应-1,0,1,自己也包括if(yyy%2){dp[x][2]=1e9;int ccc=yyy/2;//求-1ccc++;for(int i=0;i<ccc;i++) cc+=v[i].first;dp[x][0]=cc;dp[x][1]=dp[x][0]-v[ccc-1].first;}else{int ccc=yyy/2;// if(x==2) cout<<cc<<endl;for(int i=0;i<ccc;i++) cc+=v[i].first;dp[x][2]=cc;dp[x][0]=dp[x][1]=1e9;}
}
void dfs1(int root,int fa){sum[root]=1;for(int i=0;i<edge[root].size();i++){if(fa==edge[root][i]) continue;dfs1(edge[root][i],root);sum[root]+=sum[edge[root][i]];}
}
int main(){cin>>n;for(int i=1;i<=n;i++){int c,p,k;cin>>c>>p>>k;cost[i]=p;color[i]=c;for(int j=1;j<=k;j++){int x;cin>>x;rd[x]++;edge[i].push_back(x);}}for(int i=1;i<=n;i++){if(!rd[i]) root=i;}dfs1(root,-1);dfs(root,-1);cout<<min(dp[root][0],min(dp[root][1],dp[root][2]))<<endl;
}