题目描述有 $N$ 张扑克牌排成一排。卡片的编号是 $1, 2, \ldots, N$ 。卡片 $i$ 的正面写着一个整数 $A_i$ 背面写着一个整数 $B_i$ 。最初每张卡片都是正面朝上。以下操作最多可以执行 $K$ 次。- 选择满足 $1 \leq l \leq r \leq N$ 的整数 $l$ 和 $r$ 。对每个满足 $l \leq i \leq r$ 的整数 $i$ 翻转纸牌 $i$ 。这里的翻牌指的是将操作前朝下的一面翻成朝上。完成操作后求写在纸牌朝上一面的数字之和的最大可能值。解题思路1. 问题转化核心化简初始时每张卡片正面朝上第 i 张牌正面数值 \(A_i\)背面 \(B_i\)。若这张牌被翻转奇数次贡献由 \(A_i\) 变成 \(B_i\)获得增量 \(w_iB_i-A_i\)若翻转偶数次相当于没有翻转增量为 0。题目操作最多执行 k 次区间翻转每次选一段 \([l,r]\) 全部翻转。关键结论任意多次区间翻转之后最终被翻转的位置一定是若干段连续区间j 次操作最多形成 j 段连续区间。比如两次区间翻转最后翻到的区域最多分成 2 段。 因此问题等价于选出至多 k 段连续区间把区间内所有 \(w_i\) 累加求总和的最大值最后的答案 全部 \(A_i\) 的总和 选出区间的最大收益。 ans 变量一开始累加所有 a就是 \(\sum A_i\)。2.DP 状态定义对应代码里的dp数组\(dp[j][0]\)处理完前面的卡片一共用了 j 次区间操作当前第 \(i‑1\) 号卡片不在翻转区间内能得到的最大额外收益。\(dp[j][1]\)处理完前面的卡片一共用了 j 次区间操作当前第 \(i‑1\) 号卡片处在翻转区间内能得到的最大额外收益。滚动数组设计dp保存上一个卡片\(i-1\)的 DP 状态dp2用来计算当前第 i 张卡片的新状态计算结束后把dp2赋值回dp实现滚动不需要开长度 N 的数组节省空间。\(MAXK12\) 是因为题目限制 \(k\le10\)足够存放。初始条件\(dp[0][0]0\)0 张卡片0 次操作不在翻转区间收益为 0其余状态初始化为 \(-INF\)代表该状态不可选。3. 状态转移代码里核心循环遍历第 i 张卡片算出 \(wB-A\)逐个更新 j使用的操作次数\(0\le j\le k\)(1) 转移 dp2 [j][0]第 i 位不在翻转区间第 i 位不翻转那么前一位无论是在翻转区间还是不在翻转区间都可以取最大值dp2[j][0]max(dp[j][0],dp[j][1]);(2) 转移 dp2 [j][1]第 i 位处于翻转区间两种来源延续前面已经开启的翻转区间前一位 \(i-1\) 本来就在第 j 次操作的区间里现在继续翻当前卡片收益加上 w。if(dp[j][1]!-INF){ dp2[j][1]max(dp2[j][1],dp[j][1]w); }新开一段翻转区间前一位不在翻转区间现在开启第 j 段区间翻转必须消耗一次操作因此要看 \(j-1\) 的状态。此时第 i 是新区间的第一个元素收益加上 w。if(j1dp[j-1][0]!-INF){ dp2[j][1]max(dp2[j][1],dp[j-1][0]w); }(3) 更新滚动数组全部转移完成后把dp2的值赋给dpdp现在代表第 i 张卡片处理完毕后的状态进入下一张卡片循环。fr1(j,0,k){ dp[j][0]dp2[j][0]; dp[j][1]dp2[j][1]; }4. 统计答案遍历使用操作次数 \(0\le j\le k\)可以只用少于 k 次操作add取 \(dp[j][0]\) 和 \(dp[j][1]\) 的最大值也就是最多 k 次翻转可以拿到的最大额外收益最终答案初始总和 \(ans(\sum A_i)add\)。5. 复杂度分析时间复杂度\(O(n\times k)\)\(n\le2\times10^5k\le10\)运算量只有 \(2\times10^6\)完全可以通过时限空间复杂度\(O(k)\)只用两个大小为 \(12\times2\) 的数组空间开销极小。完整代码#includebits/stdc.h #define fr1(i,a,b) for(int (i)(a);(i)(b);(i)) #define fr2(i,a,b) for(int (i)(a);(i)(b);(i)--) #define fv(i,p) for(auto (i):(p)) #define ll long long #define ull unsigned ll #define pii pairint,int #define pll pairll,ll #define _1st first #define _2nd second #define elif else if #define debug coutendl-------------------------------------------------------------endl using namespace std; const ll INF 1e18; const int MAXK 12; ll dp[MAXK][2],dp2[MAXK][2],ans; int n,k; int main(){ ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cinnk; fr1(i,0,k){ dp[i][0]-INF; dp[i][1]-INF; } dp[0][0] 0; fr1(i,1,n){ ll a,b,w; cinab; ansa; wb-a; fr1(j,0,k){ dp2[j][0]-INF; dp2[j][1]-INF; } fr1(j,0,k){ dp2[j][0]max(dp[j][0],dp[j][1]); if(dp[j][1]!-INF){ dp2[j][1]max(dp2[j][1],dp[j][1]w); } if(j1dp[j-1][0]!-INF){ dp2[j][1]max(dp2[j][1],dp[j-1][0]w); } } fr1(j,0,k){ dp[j][0]dp2[j][0]; dp[j][1]dp2[j][1]; } } ll add0; fr1(j,0,k){ addmax(add,dp[j][0]); addmax(add,dp[j][1]); } coutansadd; return 0; }