题意描述

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

思路

先考虑阶段，很容易想到每个阶段是由上一行放了多少个格子转移过来的，接着考虑状态表示。

看到轮廓两个字，很容易想到杨老师的照相排列这道题，将整个轮廓作为一个状态。但是这道题的数据范围比较大，无法将整个轮廓作为状态，这个时候我们就可以找一下轮廓的某些性质。
由于寻找的是一个凸连通块，我们从行和列的方向来考虑。
\(1.\)每一行的格子个数应该是连续的，如果是间断的，显然有一段是凹进去的，不符合凸连通块的定义。
\(2.\)每一行最左边的列号应该是递增，递减或者先递减后递增的。
\(3.\)每一行最右边的列号应该是递增，递减或者先递增后递减的。

既然每一行格子的个数是连续的，所以我们可以一个区间\([l,r]\)来表示每一行选择的格子。
根据以上的性质，得到状态表示\(f[i][j][l][r][x][y]\)，表示在前\(i\)行，选择了\(j\)个格子，并且第\(i\)行选择格子的区间为\([l,r]\)，左侧状态为放缩或者扩张，右侧状态为收缩或者扩张(0缩1扩)。

设第\(i\)行选择的格子为\((l,r)\),第\(i-1\)行选择的格子为\((p,q)\),当前选择的格子和为\(a[i][r]-a[i][l-1]\),当前放了\(r-l+1\)个格子。
\(1.\)如果左右两侧都为扩张状态，那么上一行一定也要是扩张状态，且\(l≤p≤q≤r\)，枚举\(p\)和\(q\)的范围进行转移即可,转移方程为\(max(f[i-1][j-(r-l+1)][p][q][1][1]+now)\)。
\(2.\)如果左右两侧都为收缩状态，那么上一行有可能是扩张，也有可能是收缩，且\(1≤p≤l≤r≤q≤m\),枚举\(p\)和\(q\)的范围以及收缩和扩张的状态进行转移，转移方程为\(max(f[i-1][j-(r-l+1)][p][q][x][y]+now)\)。
\(3.\)如果左侧为扩张状态，右侧为收缩状态，那么左侧所对的上一行必须为扩张状态，右侧所对的上一行可能是扩张，也有可能是收缩，且\(l≤p≤r≤q≤m\)，枚举\(p\)个\(q\)的范围以及收缩和扩张的状态进行转移，转移方程为\(max(f[i-1][j-(r-l+1)][p][q][x][y])\)。
\(4.\)左侧为收缩状态，右侧为扩张状态的转移同上。

接着考虑初始值的问题，对于某一行来说，是有可能不选这一行的，所以我们定义\([m,0]\)区间表示该行一个也没放的状态。对于每个状态枚举之前，先对该状态进行初始化，即用当前这一行的\(a[i][r]-a[i][l-1]\)来表示上一行也没放时该行的状态。

对于具体的方案，我们只需要记录每个状态是由哪一个状态得到的即可，最后根据记录的状态进行倒推，得到方案。

AC代码

#include "cstring"
#include "string"
#include "vector"
#include "cmath"
#include "algorithm"
#include "map"
#include "set"
#include "queue"
#include "stack"
#include "cassert"
#include "unordered_map"
#include "sstream"
#include "cstdio"
#include "unordered_set"
#include "iomanip"

using namespace std;

#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) a.begin(),a.end()
#define rep(x,l,u) for(int x=l;x<u;x++)
#define rrep(x,l,u) for(int x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);
#define seteps(N) setprecision(N)
#define uni(x) sort(all(x)), x.erase(unique(all(x)), x.end())
#define lson (ind<<1)
#define rson (ind<<1|1) 
#define endl '\n'
#define dbg(x) cerr << #x " = " << (x) << endl
#define mp make_pair
//#define LOCAL

typedef long double lb;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
typedef pair<int,PII> PIII;
typedef pair<lb,lb> PLB;


const int N=16;
const int M=1e4+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const lll oone=1;
const double eps=1e-4;
const double pi=acos(-1);


int f[N][N*N][N][N][2][2],a[N][N],n,m,t,i,j,k,l,r,x,y,p,q,ans,now,ai,al,ar,ax,ay;
char cl[N][N*N][N][N][2][2],cr[N][N*N][N][N][2][2],dx[N][N*N][N][N][2][2],dy[N][N*N][N][N][2][2];
//1为扩张，0为放缩
void update(int dat,int L,int R,int X,int Y){
    if(dat<f[i][j][l][r][x][y]) return;
    f[i][j][l][r][x][y]=dat;
    cl[i][j][l][r][x][y]=L,cr[i][j][l][r][x][y]=R;
    dx[i][j][l][r][x][y]=X,dy[i][j][l][r][x][y]=Y;
}

void dfs(int _i,int _j,int _l,int _r,int _x,int _y){
    if(!_j) return;
    dfs(_i-1,_j-(_r-_l+1),cl[_i][_j][_l][_r][_x][_y],cr[_i][_j][_l][_r][_x][_y],dx[_i][_j][_l][_r][_x][_y],dy[_i][_j][_l][_r][_x][_y]);
    rep(j,_l,_r+1) cout<<_i<<' '<<j<<endl;
}

void solve(){
    cin>>n>>m>>t;

    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            cin>>a[i][j];
            a[i][j]+=a[i][j-1];
        }
    }


    for(i=1;i<=n;i++){
        for(j=1;j<=t;j++){
            for(l=1;l<=m;l++){
                for(r=l;r<=m;r++){
                    if((k=r-l+1)>j) break;
                    now=a[i][r]-a[i][l-1];
                    //记[m,0]表示上一行什么也没有放，枚举上一行一个不放时的max
                    for(x=0;x<2;x++){ 
                        for(y=0;y<2;y++){
                            update(now,m,0,x,y);
                        }
                    }
                    //两个边界都处于扩张状态
                    x=y=1;
                    for(p=l;p<=r;p++){
                        for(q=p;q<=r;q++){
                            update(f[i-1][j-k][p][q][1][1]+now,p,q,1,1);
                        }
                    }
                    //两个边界都处于放缩状态
                    x=y=0;
                    for(p=1;p<=l;p++){
                        for(q=r;q<=m;q++){
                            update(f[i-1][j-k][p][q][1][0]+now,p,q,1,0);
                            update(f[i-1][j-k][p][q][1][1]+now,p,q,1,1);
                            update(f[i-1][j-k][p][q][0][0]+now,p,q,0,0);
                            update(f[i-1][j-k][p][q][0][1]+now,p,q,0,1);
                        }
                    }
                    //左边界扩张,右边界放缩
                    x=1,y=0;
                    for(p=l;p<=r;p++){
                        for(q=r;q<=m;q++){
                            update(f[i-1][j-k][p][q][1][0]+now,p,q,1,0);
                            update(f[i-1][j-k][p][q][1][1]+now,p,q,1,1);
                        }
                    }
                    //左边界放缩,右边界扩张
                    x=0,y=1;
                    for(p=1;p<=l;p++){
                        for(q=l;q<=r;q++){
                            update(f[i-1][j-k][p][q][1][1]+now,p,q,1,1);
                            update(f[i-1][j-k][p][q][0][1]+now,p,q,0,1);
                        }
                    }
                }
            }
        }
    }


    for(i=1;i<=n;i++){
        for(l=1;l<=m;l++){
            for(r=1;r<=m;r++){
                for(x=0;x<2;x++){
                    for(y=0;y<2;y++){
                        if(ans<f[i][t][l][r][x][y]){
                            ans=f[i][t][l][r][x][y];
                            ai=i,al=l,ar=r,ax=x,ay=y;
                        }
                    }
                }
            }
        }
    }

    cout<<"Oil : "<<ans<<endl;
    dfs(ai,t,al,ar,ax,ay);
}

int main(){
    IOS;
    //cout<<fixed<<seteps(2);
#ifdef LOCAL
    freopen("data.in","r",stdin);
#endif
    int t=1;
    //scanf("%d",&t);
    rep(i,1,t+1){
        solve();
    }
}