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 0
for(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 0
for(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 1
for(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;
}
来源：https://www./content-4-762451.html
|
