[AGM 2022 资格赛] 分裂 题解洛谷链接记得点赞前言一道十分有意思的小题。分析观察这个式子可以考虑使用 DP。令d p i , j dp_{i,j}dpi,j表示前i ii个元素已经划分了j jj个非空子段的最大得分。直接写出状态转移d p i , j max k j − 1 i − 1 ( d p k , j − 1 [ max p k 1 i ( a p ) ] b j − [ min p k 1 i ( a p ) ] b j ) dp_{i,j}\max_{kj-1}^{i-1}(dp_{k,j-1}[\max_{pk1}^i(a_p)]^{b_j}-[\min_{pk1}^i(a_p)]^{b_j})dpi,jkj−1maxi−1(dpk,j−1[pk1maxi(ap)]bj−[pk1mini(ap)]bj)显然这是O ( n 4 ) O(n^4)O(n4)的时间复杂度即使使用 ST 表优化查询也会达到O ( n 3 ) O(n^3)O(n3)会超时。仔细一看发现转移只跟最大值与最小值有关。所以答案就成了选择K KK个点对的最大得分。状态定义令d p i , j , k dp_{i,j,k}dpi,j,k表示前i ii个元素已经开始划分第j jj个非空子段状态为k kk的最大得分。其中k kk的含义为若k 0 k0k0则表示所有的点对已经配对。若k 1 k1k1则表示仅配对了最大值。若k 2 k2k2则表示仅配对了最小值。根据定义答案就是d p n , K , 0 dp_{n,K,0}dpn,K,0。状态转移显然选取最大值a i a_iai的贡献是a i b j a_i^{b_j}aibj最小值的贡献是− a i b j -a_i^{b_j}−aibj。对于每一个状态k kk除了不选有如下的转移路径k 0 k0k0时可以独成一段或从k 1 k1k1或从k 2 k2k2转移。k 1 k1k1或k 2 k2k2时可以从闭合状态转移。初始化因为可能出现负数显然需要将d p dpdp数组初始化为极小值。此外由于在枚举i ii时k 0 k0k0时转移会访问到d p i , 0 , 0 dp_{i,0,0}dpi,0,0所以需要初始化d p i , 0 , 0 dp_{i,0,0}dpi,0,0为0 00。参考代码#includebits/stdc.h#defineintlonglongusingnamespacestd;intn,k;inta[5010],b[5010];intdp[3][5010][5];intfpow(intx,inty){intres1;while(y){if(y1)res*x;x*x;y1;}returnres;}signedmain(){memset(dp,0xc0,sizeof(dp));cinnk;for(inti1;in;i){cina[i];}for(inti1;ik;i){cinb[i];}for(inti0;in;i){dp[i][0][0]0;}for(inti1;in;i){for(intj1;jmin(k,i);j){dp[i1][j][0]max({dp[(i-1)1][j][0],dp[(i-1)1][j-1][0],dp[(i-1)1][j][1]-fpow(a[i],b[j]),dp[(i-1)1][j][2]fpow(a[i],b[j])});dp[i1][j][1]max({dp[(i-1)1][j][1],dp[(i-1)1][j-1][0]fpow(a[i],b[j])});dp[i1][j][2]max({dp[(i-1)1][j][2],dp[(i-1)1][j-1][0]-fpow(a[i],b[j])});//要么不选要么选}}coutdp[n1][k][0];return0;}by lonys