​Problem - 2174B - Codeforces​[DP优化]

Problem - 2174B - Codeforces求经过n个朋友的最大值问题我们可以考虑dp对于每个朋友 我们关心的有 剩余的卡片或者已经用了的卡片 二者之间可以互推导 前缀最大值所以我们可以写出一个朴素的dp :记dp[i,j,k]表示送完第i个朋友的时候 剩下j张卡片 并且前缀最大值为k的时候 最大快乐为dp[i,j,k]然后转移的方法 遍历i j k 枚举该位置用了多少张卡片 时间复杂度o(nk^3);显然这样是一定会TLE的 因此我们要进行优化我们观察可以发现 如果后面某次进行的操作比前缀最大值小或者相等 那么这次操作是无意义的 因此我们要保证每次给予卡片都要更新前缀最大值 所以我们要维护一个上限单调递增的序列 而中间递减的部分 我们给予0 卡片 这样一定不会更劣 所以我们只需要从前往后遍历 只筛选前缀最大值改变的点进行操作即可所以我们重新设计dp的状态进行优化 令dp[k,j]表示前缀最大值为k的时候 剩余卡片为j的最大快乐 然后进行转移 用下标的差计算中间空缺的部分的快乐值代码实现如下#include bits/stdc.h using namespace std; void solve(){ int n,k; cinnk; int ma0; vectorinta(n1,0); vectorintid;id.push_back(0); for(int i1;in;i){ cina[i]; if(a[i]ma){//存递增点 maa[i]; id.push_back(i); } } vectorvectorintdp(k1,vectorint(k1,-1)); //花费j张卡 最大值为j2 的快乐值 dp[0][0]0; for(int i1;iid.size();i){ for(int jk;j0;j--){ //枚举花费 int mx-1; for(int j20;j2k;j2){ mxmax(mx,dp[j][j2]); } if(mx0)continue;//没有合法状态 跳过 for(int j20;j2a[id[i]]j2jk;j2){//枚举最大值转移 dp[jj2][j2]max(dp[jj2][j2],mx); } } int nxt(i1id.size())?id[i1]:n1; //下一个递增点 int ccnxt-id[i]; //区间距离 for(int j0;jk;j){ for(int j20;j2k;j2){ if(dp[j][j2]0){ //合法的话 补上到下一个合法点之间的快乐值 dp[j][j2]j2*cc; } } } } int ans0; for(int j0;jk;j){ for(int j20;j2k;j2){ ansmax(ans,dp[j][j2]); } } coutans\n; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cint; while(t--)solve(); return 0; }