题目描述：

【题意】 在 N*M 的矩阵中，每个格子有一个权值，要求寻找一个包含 K 个格子的凸连通块（连通块中间没有空缺，并且轮廓是凸的），使这个连通块中的格子的权值和最大。

注意：凸连通块是指：连续的若干行，每行的左端点列号先递减、后递增，右端点列号先递增、后递减。 求出这个最大的权值和，并给出连通块的具体方案，输出任意一种方案即可。 【输入格式】 第一行包含三个整数N,M和K。 接下来N行每行M个整数，表示N*M的矩阵上每个格子的权值（均不超过1000）。 【数据范围】 1<=n,m<=15 【输入样例】 2 3 4 10 20 30 40 2 3 【输出样例】 Oil : 100 1 1 1 2 1 3 2 1

抓住问题的本质，每行的左端点列号先递减、后递增，右端点列号先递增、后递减。虽然这显然不是凸连通块的定义，（比如十字架也满足这个条件，但是它不是凸连通块）但既然出题人的数学没有学好，我们就将错就错了

动态规划问题要抓住两个本质

第一：状态表示。这里我们用f[i][j][l][r][x][y]表示当前走到第i行，一共选了j个，第i行选了l~r，它左右端点的增减状态分别是x和y。这样做的原因有以下：1.此类矩阵问题需要一行一行处理，因此我们要有 i 这个集合状态  2.题目对选择格子数有严格的要求（=k），这就要求我们设置 j 去保证状态转移以及结果的正确性  3.为维持凸连通图的状态，我们需要知道当前行的左右端点，这要求我们设置l 和 r去描述当前行，并通过x 和 y 了解当前行相对于上一行的状态。欸，我们掐指一算发现没有爆空间第二：状态转移这里我们分别就，当前行的x、y的取值分类讨论。假设0为编号递减，1为编号递增（注意这里的递增递减是非严格的，这意味着一个矩形也可以是凸连通块）0 1 状态就是左端点递减，右端点递增，也就是八字形。1 0 状态就是左端点递增，右端点递减，也就是V字形。0 0 状态就是左端点递减，右端点递减1 1 状态就是左端点递增，右端点递增有人可能会问：如果当前行的左端点编号等于上一行的左端点编号，并且当前行的右端点编号等于上一行的右端点编号，怎么办？其实很简单，因为递增递减的概念是非严格的，所以这种情况既属于0 1，也属于 1 0，同时也属于 0 0 和1 1，重复了也没有太大影响接下来就是分类讨论的时候因为左端点一定要先递减后递增，换句话说递增可以继承递减和递增，但是递减只能继承递减（否则不满足凸连通块）也就是 1 可以继承 0 和 1 ，但是 0 一定只能继承 0因为右端点一定要先递增后递减，换句话说递减可以继承递减和递增，但是递增只能继承递增（否则不满足凸连通块）也就是 0 可以继承 0 和 1，但是 1 一定只能继承 1综上所述：0 1 状态只能继承上一行的 0 1 状态1 0 状态可以继承上一行的0 0 、0 1、 1 0、 11 状态0 0 状态可以继承上一行的0 0 和 0 1 状态1 1 状态可以继承上一行的1 1 和 0 1 状态当然其他也很好推比如上一行的 i 就是 当前i-1上一行的 j 就是 j-(r-l+1)上一行的l 和 r 根据边界、当前的 l 和 r  以及 x 和 y 的不同来枚举对于最后要输出各个点的要求，我们可以直接开一个数组去记录每一个状态的继承方向，在最后一路回溯即可

最后代码如下：

（可以压缩的东西很多，但是我没有刻意简化，所以代码很丑，见谅）

这里还有个小错误，就是如果最后的答案只有一行的点的话，就可能没有记录。因为代码已经太长我懒得再写了，而且我估计没有这样的数据点（事实证明我是对的），当然补上也不难

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; inline int read() { char c=getchar();int f=1,s=0; while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){s=s*10+c-'0';c=getchar();} return f*s; } int n,m,k; int f[16][250][16][16][2][2],a[16][16],sum[16][16]; struct node { int l,r,x,y; // node(int ll=0,int rr=0,int xx=0,int yy=0){l=ll;r=rr;x=xx;y=yy;} }d[16][250][16][16][2][2]; struct putout { int i,j,l,r,x,y,d; // putout(int ii=0,int jj=0,int ll=0,int rr=0,int xx=0,int yy=0,int dd=0){i=ii;j=jj;l=ll;r=rr;x=xx;y=yy;d=dd;} }ans; inline int mymin(int x,int y){return x<y?x:y;} inline int mymax(int x,int y){return x>y?x:y;} int main() { n=read();m=read();k=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read(),sum[i][j]=sum[i][j-1]+a[i][j]; ans.d=0; for(int i=1;i<=n;i++)//当前进行到第几行 { for(int j=1;j<=mymin(i*m,k);j++)//当前一共选了多少个 { for(int l=1;l<=m;l++) { for(int r=l;r<=mymin(m,l+j-1);r++) { int snow=sum[i][r]-sum[i][l-1]; if(r-l+1>j)break; if(snow>f[i][j][l][r][0][0]) { f[i][j][l][r][0][0]=snow; d[i][j][l][r][0][0]={0,0,-1,-1}; } if(snow>f[i][j][l][r][0][1]) { f[i][j][l][r][0][1]=snow; d[i][j][l][r][0][1]={0,0,-1,-1}; } if(snow>f[i][j][l][r][1][0]) { f[i][j][l][r][1][0]=snow; d[i][j][l][r][1][0]={0,0,-1,-1}; } if(snow>f[i][j][l][r][1][1]) { f[i][j][l][r][1][1]=snow; d[i][j][l][r][1][1]={0,0,-1,-1}; } if(i==1)continue; //x=0,y=1; { for(int p=l;p<=r;p++) { for(int q=p;q<=r;q++) { if(q-p+1+r-l+1>j)break; if(f[i-1][j-(r-l+1)][p][q][0][1]+snow>f[i][j][l][r][0][1]) { f[i][j][l][r][0][1]=f[i-1][j-(r-l+1)][p][q][0][1]+snow; d[i][j][l][r][0][1]={p,q,0,1}; } if(f[i][j][l][r][0][1]>ans.d) ans={i,j,l,r,0,1,f[i][j][l][r][0][1]}; } } } //x=1,y=0; { for(int p=l;p>=1;p--) { if(r-p+1+r-l+1>j)break; for(int q=r;q<=m;q++) { if(q-p+1+r-l+1>j)break; if(f[i-1][j-(r-l+1)][p][q][1][0]+snow>f[i][j][l][r][1][0]) { f[i][j][l][r][1][0]=f[i-1][j-(r-l+1)][p][q][1][0]+snow; d[i][j][l][r][1][0]={p,q,1,0}; } if(f[i-1][j-(r-l+1)][p][q][1][1]+snow>f[i][j][l][r][1][0]) { f[i][j][l][r][1][0]=f[i-1][j-(r-l+1)][p][q][1][1]+snow; d[i][j][l][r][1][0]={p,q,1,1}; } if(f[i-1][j-(r-l+1)][p][q][0][0]+snow>f[i][j][l][r][1][0]) { f[i][j][l][r][1][0]=f[i-1][j-(r-l+1)][p][q][0][0]+snow; d[i][j][l][r][1][0]={p,q,0,0}; } if(f[i-1][j-(r-l+1)][p][q][0][1]+snow>f[i][j][l][r][1][0]) { f[i][j][l][r][1][0]=f[i-1][j-(r-l+1)][p][q][0][1]+snow; d[i][j][l][r][1][0]={p,q,0,1}; } if(f[i][j][l][r][1][0]>ans.d) ans={i,j,l,r,1,0,f[i][j][l][r][1][0]}; } } } //x=0,y=0; { for(int p=l;p<=r;p++) { for(int q=r;q<=m;q++) { if(q-p+1+r-l+1>j)break; if(f[i-1][j-(r-l+1)][p][q][0][0]+snow>f[i][j][l][r][0][0]) { f[i][j][l][r][0][0]=f[i-1][j-(r-l+1)][p][q][0][0]+snow; d[i][j][l][r][0][0]={p,q,0,0}; } if(f[i-1][j-(r-l+1)][p][q][0][1]+snow>f[i][j][l][r][0][0]) { f[i][j][l][r][0][0]=f[i-1][j-(r-l+1)][p][q][0][1]+snow; d[i][j][l][r][0][0]={p,q,0,1}; } if(f[i][j][l][r][0][0]>ans.d) ans={i,j,l,r,0,0,f[i][j][l][r][0][0]}; } } } //x=1,y=1; { for(int p=l;p>=1;p--) { for(int q=r;q>=l;q--) { if(q-p+1+r-l+1>j)break; if(f[i-1][j-(r-l+1)][p][q][1][1]+snow>f[i][j][l][r][1][1]) { f[i][j][l][r][1][1]=f[i-1][j-(r-l+1)][p][q][1][1]+snow; d[i][j][l][r][1][1]={p,q,1,1}; } if(f[i-1][j-(r-l+1)][p][q][0][1]+snow>f[i][j][l][r][1][1]) { f[i][j][l][r][1][1]=f[i-1][j-(r-l+1)][p][q][0][1]+snow; d[i][j][l][r][1][1]={p,q,0,1}; } if(f[i][j][l][r][1][1]>ans.d) ans={i,j,l,r,1,1,f[i][j][l][r][1][1]}; } } } } } } } printf("Oil : %d\n",ans.d); int i=ans.i,j=ans.j,l=ans.l,r=ans.r,x=ans.x,y=ans.y; while(i && x!=-1 && y!=-1) { for(int tt=l;tt<=r;tt++)printf("%d %d\n",i,tt); int ll,rr,xx,yy; ll=d[i][j][l][r][x][y].l; rr=d[i][j][l][r][x][y].r; xx=d[i][j][l][r][x][y].x; yy=d[i][j][l][r][x][y].y; i--;j-=(r-l+1); l=ll;r=rr;x=xx;y=yy; } return 0; }