[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_{k=j-1}^{i-1}(dp_{k,j-1}+[\max_{p=k+1}^i(a_p)]^{b_j}-[\min_{p=k+1}^i(a_p)]^{b_j})dpi,j​=k=j−1maxi−1​(dpk,j−1​+[p=k+1maxi​(ap​)]bj​−[p=k+1mini​(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 k=0k=0，则表示所有的点对已经配对。
• 若k = 1 k=1k=1，则表示仅配对了最大值。
• 若k = 2 k=2k=2，则表示仅配对了最小值。

根据定义，答案就是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 k=0k=0时，可以独成一段或从k = 1 k=1k=1或从k = 2 k=2k=2转移。
• k = 1 k=1k=1或k = 2 k=2k=2时，可以从闭合状态转移。

初始化

因为可能出现负数，显然需要将d p dpdp数组初始化为极小值。

此外，由于在枚举i ii时，k = 0 k=0k=0时转移会访问到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。

参考代码

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intn,k;inta[5010],b[5010];intdp[3][5010][5];intfpow(intx,inty){intres=1;while(y){if(y&1)res*=x;x*=x;y>>=1;}returnres;}signedmain(){memset(dp,0xc0,sizeof(dp));cin>>n>>k;for(inti=1;i<=n;i++){cin>>a[i];}for(inti=1;i<=k;i++){cin>>b[i];}for(inti=0;i<=n;i++){dp[i][0][0]=0;}for(inti=1;i<=n;i++){for(intj=1;j<=min(k,i);j++){dp[i&1][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[i&1][j][1]=max({dp[(i-1)&1][j][1],dp[(i-1)&1][j-1][0]+fpow(a[i],b[j])});dp[i&1][j][2]=max({dp[(i-1)&1][j][2],dp[(i-1)&1][j-1][0]-fpow(a[i],b[j])});//要么不选，要么选}}cout<<dp[n&1][k][0];return0;}

by lonys