CH5104题解
CH5104：I-Country题解（线性DP）
MDZZ这道题调了2个小时自闭了（（
题意简述
给你一个\(N*M\)的矩阵，每个格子都有一个权值。现在让你寻找一个包含\(K\)个格子的凸连通块，使得这个连通块的权值之和最大，求出这个最大的权值和，并给出连通块的具体方案。
题意分析
这道题主要难理解的东西就是凸连通块。
凸连通块是什么意思呢？就是整个图形的外轮廓不能突然凹下去一块，中间也不能有空缺。理性的说，任意两点连成的线段，如果经过图形，那么只能经过一个部分，不可能进去\(\to\)出来\(\to\)又进去。
总结：我们把这个连通块分成若干行，每行的左端点列号先递减，后递增；右端点列号先递增，后递减；满足单调性。
题目分析
这道题真的很F**K
首先，我们可以看出这是一道\(DP\)的题。
我们需要关注那些信息呢？
\((1)\).当前已经处理过了多少行；
\((2)\).已经选拔出了多少个格子；
\((3)\).当前行已选的格子的左端点——用于确定下一行左端点的可行范围；
\((4)\).当前行已选的格子的右端点——用于确定下一行右端点的可行范围；
\((5).\)当前左侧轮廓的单调性类型；
\((6).\)当前右侧轮廓的单调性类型；
好吧我得实话告诉你这些东西都要记录在\(dp\)数组中（啊这~）。
由此我们定义状态：\(dp_{i,j,l,r,x,y}\)
这个状态表示：前\(i\)行总共已经选了\(j\)个格子，其中第\(i\)行选择了第\(l\)到\(r\)个格子（均为\(0\)表示都不选），左边界的单调性为\(x\)，右边界的单调性为\(y\)时能构成的连通块的最大权值之和。 （\(0\)表示递增，\(1\)表示递减）
这道题的状态转移方程挺好理解的，如下：
\((1).\)左边界的列号递减，右边界的列号递增（此时两个边界都处于扩张状态）
\(if \space \space j=r-l 1>0:\) \(dp_{i,j,l,r,1,0}=\sum^{r}_{p=l}A_{i,p} dp_{i-1,0,0,0,1,0}\)
\(if \space \space j>r-l 1>0:\) \(dp_{i,j,l,r,1,0}=\sum^{r}_{p=l}A_{i,p} max_{l\le p\le q\le r} {dp_{i-1,j-(r-l 1),p,q,1,0}}\)
\((2).\)左右的列号都递减（左边界扩张，右边界收缩）
\(dp_{i,j,l,r,1,1}=\sum^r_{p=l} \max_{l\le p \le r \le q} {\max_{0\le y \le 1}} {dp_{i-1,j-(r-l 1),p,q,1,y}}\)
\((3).\)左右的列号都递增（左边界收缩，右边界扩张）
\(dp_{i,j,l,r,0,0}=\sum^r_{p=l} \max_{p\le l \le q \le r} {\max_{0\le x \le 1}} {dp_{i-1,j-(r-l 1),p,q,x,0}}\)
\((4).\)左边界的列号递增，右边界的列号递减（此时两个边界都处于收缩状态）
\(dp_{i,j,l,r,0,1}={\sum^r_{p=l}A_{i,p} \max_{p\le l \le r \le q}{\max_{0\le x \le 1}}{\max_{0\le y\le 1}dp_{i-1,j-(r-l 1),p,q,x,y}}}\)
很明显初始状态\(dp_{i,0,0,0,1,0}=0\)，目标状态是\(\max dp_{i,K,l,r,x,y}\)，时间复杂度\(\Theta (NM^4K)=\Theta (N^2M^5)\)
#include<bits/stdc .h>using namespace std;const int N=20;struct path{int i,k,l,fl,r,fr;}pre[N][N*N][N][2][N][2],anss;int n,m,K,ans;int mp[N][N],sum[N][N];int dp[N][N*N][N][2][N][2];void print(path x){if(x.l==x.r && x.l==0) return;for(int i=x.l;i<=x.r;i ) printf("%d %d\n",x.i,i);print(pre[x.i][x.k][x.l][x.fl][x.r][x.fr]);}int read(){ int x=0,f=1; char c=getchar(); while (c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while (c>='0'&&c<='9') { x=(x<<1) (x<<3) (c^48); c=getchar(); } return x*f;}int main(){scanf("%d%d%d",&n,&m,&K);for(int i=1;i<=n;i ) for(int j=1;j<=m;j ) mp[i][j]=read(),sum[i][j]=sum[i][j-1] mp[i][j];for(int i=1;i<=n;i ) { for(int k=1;k<=K;k ) { for(int l=1;l<=m;l ) { for(int r=l;r<=m;r ){int len=r-l 1,val=sum[i][r]-sum[i][l-1];if(len>k) continue;if(len==k){dp[i][k][l][0][r][0]=val;pre[i][k][l][0][r][0]=path{0,0,0,0,0,0};if(dp[i][k][l][0][r][0]>ans){ans=dp[i][k][l][0][r][0];anss=path{i,k,l,0,r,0};}continue;}for(int l1=l;l1<=r;l1 ) { for(int r1=l1;r1<=r;r1 ){int len1=r1-l1 1;if(len1>k-len) continue;if(dp[i-1][k-len][l1][0][r1][0] val>dp[i][k][l][0][r][0]){dp[i][k][l][0][r][0]=dp[i-1][k-len][l1][0][r1][0] val;pre[i][k][l][0][r][0]=path{i-1,k-len,l1,0,r1,0};}if(dp[i][k][l][0][r][0]>ans){ans=dp[i][k][l][0][r][0];anss=path{i,k,l,0,r,0};}} }//0 0for(int l1=1;l1<=l;l1 ) { for(int r1=l;r1<=r;r1 ){int len1=r1-l1 1;if(len1>k-len) continue;if(dp[i-1][k-len][l1][0][r1][0] val>dp[i][k][l][1][r][0]){dp[i][k][l][1][r][0]=dp[i-1][k-len][l1][0][r1][0] val;pre[i][k][l][1][r][0]=path{i-1,k-len,l1,0,r1,0};}if(dp[i-1][k-len][l1][1][r1][0] val>dp[i][k][l][1][r][0]){dp[i][k][l][1][r][0]=dp[i-1][k-len][l1][1][r1][0] val;pre[i][k][l][1][r][0]=path{i-1,k-len,l1,1,r1,0};}if(dp[i][k][l][1][r][0]>ans){ans=dp[i][k][l][1][r][0];anss=path{i,k,l,1,r,0};}} }//1 0for(int l1=l;l1<=r;l1 ) { for(int r1=r;r1<=m;r1 ){int len1=r1-l1 1;if(len1>k-len) continue;if(dp[i-1][k-len][l1][0][r1][0] val>dp[i][k][l][0][r][1]){dp[i][k][l][0][r][1]=dp[i-1][k-len][l1][0][r1][0] val;pre[i][k][l][0][r][1]=path{i-1,k-len,l1,0,r1,0};}if(dp[i-1][k-len][l1][0][r1][1] val>dp[i][k][l][0][r][1]){dp[i][k][l][0][r][1]=dp[i-1][k-len][l1][0][r1][1] val;pre[i][k][l][0][r][1]=path{i-1,k-len,l1,0,r1,1};}if(dp[i][k][l][0][r][1]>ans){ans=dp[i][k][l][0][r][1];anss=path{i,k,l,0,r,1};}} }//0 1for(int l1=1;l1<=l;l1 ) { for(int r1=r;r1<=m;r1 ){int len1=r1-l1 1;if(len1>k-len) continue;if(dp[i-1][k-len][l1][0][r1][0] val>dp[i][k][l][1][r][1]){dp[i][k][l][1][r][1]=dp[i-1][k-len][l1][0][r1][0] val;pre[i][k][l][1][r][1]=path{i-1,k-len,l1,0,r1,0};}if(dp[i-1][k-len][l1][0][r1][1] val>dp[i][k][l][1][r][1]){dp[i][k][l][1][r][1]=dp[i-1][k-len][l1][0][r1][1] val;pre[i][k][l][1][r][1]=path{i-1,k-len,l1,0,r1,1};}if(dp[i-1][k-len][l1][1][r1][0] val>dp[i][k][l][1][r][1]){dp[i][k][l][1][r][1]=dp[i-1][k-len][l1][1][r1][0] val;pre[i][k][l][1][r][1]=path{i-1,k-len,l1,1,r1,0};}if(dp[i-1][k-len][l1][1][r1][1] val>dp[i][k][l][1][r][1]){dp[i][k][l][1][r][1]=dp[i-1][k-len][l1][1][r1][1] val;pre[i][k][l][1][r][1]=path{i-1,k-len,l1,1,r1,1};}if(dp[i][k][l][1][r][1]>ans){ans=dp[i][k][l][1][r][1];anss=path{i,k,l,1,r,1};}} }//1 1} } } }printf("Oil : %d\n",ans);print(anss);return 0;}