在 N×MN×M 的矩阵中，每个格子有一个权值，要求寻找一个包含 KK 个格子的凸连通块（连通块中间没有空缺，并且轮廓是凸的），使这个连通块中的格子的权值和最大。
注意：凸连通块是指：连续的若干行，每行的左端点列号先递减、后递增，右端点列号先递增、后递减。
求出这个最大的权值和，并给出连通块的具体方案，输出任意一种方案即可。
输入格式
第一行包含三个整数 N,MN,M 和 KK。
接下来 NN 行每行 MM 个整数，表示 N×MN×M 的矩阵上每个格子的权值（均不超过 10001000）。
输出格式
第一行输出 Oil : X，其中 XX 为最大权值和。
接下来 KK 行每行两个整数 xixi 和 yiyi，用来描述所有格子的具体位置，每个格子位于第 xixi 行，第 yiyi 列。
数据范围
1≤N,M≤151≤N,M≤15,
0≤K≤N×M0≤K≤N×M
输入样例：
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表示，大了用0表示，所以左端点往外伸/缩的状态对应x=1/0，右端点往外伸/缩的状态对应y=0/1。
状态计算：根据x,y的取值可以分为4种状态，每一种状态的的前一步是不同的。记当前的状态为f[i]][j][l][r][x][x]。（x表示待确定）
1、左扩张，右扩张。此时x=1，y=0,因为题目告诉我们围成的图形的特点（是一个凸连通块），所以如果当前的趋势左右端点都是扩张的话，那它的上一步一定也是扩张，所以它的上一步就是f[i-1][j-(r-l+1)][p][q][1][0]，下一个难点就是p，q的取值范围（p是上一行选择的左端点，q是右端点），其满足l<=p<=q<=r（想想一下当前情况对应的形状就能比较容易得到了）
2、左扩张，右收缩。x=y=1,如果左边是扩张的话那么它的上一步就一定是扩张，上一步x=1,而当前右边是收缩的，它的上一步可能是扩张的，也可能是收缩的，有两种状态,上一步y=0/1，满足l<=p<=r<=q。
3、左收缩，右扩张。x=y=0,左边收缩上一步可以是收缩也可以是扩张，右扩张，上一步只能是扩张，此时满足p<=l<=q<=r
4、左收缩，右收缩,x=0,y=1，左右两边上一步都既可以是收缩也可以是扩张，此时满足p<=l<=r<=q。
根据上面四种情况得到上一步的最大值后，再加上当前一行选择的数就是当前状态的值。
上代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=16;
int n,m,k;
int w[N][N];
int f[N][N*N][N][N][2][2];
struct State
{
int i,j,l,r,x,y;
}g[N][N*N][N][N][2][2];
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>w[i][j];
memset(f,-0x3f3f3f3f,sizeof f);
for(int i=1;i<=n;i++)
for(int j=0;j<=k;j++)
for(int l=1;l<=m;l++)
for(int r=1;r<=m;r++)
{
if(j<r-l+1)
continue;
//左扩张，右扩张
{
auto &vf=f[i][j][l][r][1][0];
auto &vg=g[i][j][l][r][1][0];
if(j==r-l+1)
vf=0;
for(int p=l;p<=r;p++)
for(int q=p;q<=r;q++)
{
int val=f[i-1][j-(r-l+1)][p][q][1][0];
if(val>vf)
{
vf=val;
vg={i-1,j-(r-l+1),p,q,1,0};
}
}
for(int u=l;u<=r;u++)
vf+=w[i][u];
}
//左扩张，右收缩
{
auto &vf=f[i][j][l][r][1][1];
auto &vg=g[i][j][l][r][1][1];
// if(j==r-l+1)
// vf=0;
for(int p=l;p<=r;p++)
for(int q=r;q<=m;q++)
for(int y=0;y<=1;y++)
{
int val=f[i-1][j-(r-l+1)][p][q][1][y];
if(val>vf)
{
vf=val;
vg={i-1,j-(r-l+1),p,q,1,y};
}
}
for(int u=l;u<=r;u++)
vf+=w[i][u];
}
// 左收缩，右扩张
{
auto &vf=f[i][j][l][r][0][0];
auto &vg=g[i][j][l][r][0][0];
// if(j==r-l+1)
// vf=0;
for(int p=1;p<=l;p++)
for(int q=l;q<=r;q++)
for(int x=0;x<=1;x++)
{
int val=f[i-1][j-(r-l+1)][p][q][x][0];
if(val>vf)
{
vf=val;
vg={i-1,j-(r-l+1),p,q,x,0};
}
}
for(int u=l;u<=r;u++)
vf+=w[i][u];
}
//左收缩，右收缩
{
auto &vf=f[i][j][l][r][0][1];
auto &vg=g[i][j][l][r][0][1];
// if(j==r-l+1)
// vf=0;
for(int p=1;p<=l;p++)
for(int q=r;q<=m;q++)
for(int x=0;x<=1;x++)
for(int y=0;y<=1;y++)
{
int val=f[i-1][j-(r-l+1)][p][q][x][y];
if(val>vf)
{
vf=val;
vg={i-1,j-(r-l+1),p,q,x,y};
}
}
for(int u=l;u<=r;u++)
vf+=w[i][u];
}
}
int res=0;
State state;
for(int i=1;i<=n;i++)
for(int l=1;l<=m;l++)
for(int r=1;r<=m;r++)
for(int x=0;x<=1;x++)
for(int y=0;y<=1;y++)
{
int val=f[i][k][l][r][x][y];
if(val>res)
{
res=val;
state={i,k,l,r,x,y};
}
}
printf("Oil : %d\n", res);
while(state.j)
{
for(int i=state.l;i<=state.r;i++)
cout<<state.i<<" "<<i<<endl;
state=g[state.i][state.j][state.l][state.r][state.x][state.y];
}
return 0;
}
