C++14(g++5.4) 解法, 执行用时: 80ms, 内存消耗: 44552K, 提交时间: 2020-07-08 16:34:03

#include <bits/stdc++.h>
using namespace std;
const int maxn = 17;
#define now dp[i][l][r][k][x][y]
#define to dp[i+1][L][R][k+R-L]
#define tr re[i+1][L][R][k+R-L]
#define add mp[i+1][R-1]-mp[i+1][L-1]
int N, M, K, i, l, r, j, k, x, y, up, lf, ri, L, R, v;
int ans, ii, ll, rr, jj, kk, xx, yy;
int mp[maxn][maxn], tmp[4];
int dp[maxn][maxn][maxn][maxn*maxn][2][2];
int re[maxn][maxn][maxn][maxn*maxn][2][2][4];
vector<int> loc[maxn];
inline void change()
{
	if (k==K&&ans<now){ii = i; ll = l; rr = r; xx = x; yy = y; ans = now;}
}
inline void tran(int tx, int ty)
{
	if (k+R-L<=K&&to[tx][ty]<now+add){to[tx][ty] = now+add;tr[tx][ty][0] = l;tr[tx][ty][1] = r;tr[tx][ty][2] = x;tr[tx][ty][3] = y;}
}
inline void work()
{
	if (now==-1) return; //状态不存在 
	change();
	if (k==K) return;// 无需再转移
	lf = x ? l : l+1;// 向11转移
	ri = y ? r : r-1;// L>=lf && L < ri && R>=L+1 && R<=ri 
	for (L = lf; L < ri; ++L)// xx to 11
		for (R = L+1; R <= ri; ++R)
			tran(1, 1);
	if (!x)// 00|01 to 01
	for (L = 1; L <= l; ++L)
		for (R = l+1; R <= ri; ++R)
			tran(0, 1);
	if (!y)// 10|00 to 10
	for (L = lf; L < r; ++L)
		for (R = r; R <= M+1; ++R)
			tran(1, 0);
	if (!x&&!y)// 00 to 00
	for (L = 1; L <= l; ++L)
		for (R = r; R <= M+1; ++R)
			tran(0, 0);
}
int main()
{
	scanf("%d %d %d", &N, &M, &K);
	for (i = 1; i <= N; ++i)
		for (j = 1; j <= M; ++j)
			scanf("%d", &v), mp[i][j] = mp[i][j-1] + v;
	if (!K){puts("Oil : 0");return 0;}
	memset(dp, -1, sizeof(dp));
	i = 0; k = 0;
	for (l = 1; l <= M; ++l)
		for (x = 0; x < 2; ++x)
			for (y = 0; y < 2; ++y)
				if (!(x&&y))
					dp[0][l][r=l][0][x][y] = 0, work();
	for (i = 1; i <= N; ++i)
		for (l = 1; l <= M; ++l)
			for (r = l; r <= M+1; ++r)
				for (k = r-l, up = min((i-1)*M+r-l, K); k <= up; ++k)
					for (x = 0; x < 2; ++x)
						for (y = 0; y < 2; ++y)
							work();
	printf("Oil : %d\n", ans);
	int en = ii;
	kk = K;
	while (ii)
	{
		if (rr-ll)
			loc[ii].push_back(ll), loc[ii].push_back(rr);
		else
			break;
		memcpy(tmp, re[ii][ll][rr][kk][xx][yy], sizeof(tmp));
		kk -= rr-ll;
		ii--;
		ll = tmp[0];
		rr = tmp[1];
		xx = tmp[2];
		yy = tmp[3];
	}
	for (i = ii+1; i <= en; ++i)
		for (j = loc[i][0]; j < loc[i][1]; ++j)
			printf("%d %d\n", i, j); 
	return 0;
}
/*
2 3 4 
10 20 30 
40 2 3

Oil : 100 
1 1 
1 2 
1 3 
2 1
*/

C++(g++ 7.5.0) 解法, 执行用时: 203ms, 内存消耗: 62948K, 提交时间: 2023-03-30 17:09:08

#include<cstdio>
#include<cstring>
#define _rep(i,a,b) for(i=(a);i<=(b);i++)
#define _for(i,a,b) for(i=(a);i<(b);i++)
int n,m,K,now,l,r,x,y,i,j,p,q,k,si,sl,sr,sx,sy,ans;
int a[16][16],sum[16][16],f[16][226][16][16][2][2];
//f[i][j][l][r][x][y]表示前i行选择j个格子吗，其中第i行选择了第l到r个格子（m到0不选——
//x=0表示左边界收缩，x=1表示左边界扩张， y同理 
struct node{
    int l,r,x,y;
}S[16][226][16][16][2][2];
inline void update(int dat,int L,int R,int X,int Y)
{
    if(dat<f[i][j][l][r][x][y])return;
    node &s=S[i][j][l][r][x][y];
    f[i][j][l][r][x][y]=dat,s.l=L,s.r=R,s.x=X,s.y=Y;
}
void print(int i,int j,int l,int r,int x,int y)
{
    if(!j)return;node &s=S[i][j][l][r][x][y];
    print(i-1,j-(r-l+1),s.l,s.r,s.x,s.y);
    _rep(j,l,r)printf("%d %d\n",i,j);
}
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d%d%d",&n,&m,&K);memset(f,0xcf,sizeof(f));
    _rep(i,1,n)_rep(j,1,m)scanf("%d",&a[i][j]),sum[i][j]=sum[i][j-1]+a[i][j];
    _rep(i,1,n)_rep(j,1,K)_rep(l,1,m)_rep(r,l,m)
    {
        k=r-l+1;if(k>j)break;
        now=sum[i][r]-sum[i][l-1];
        _for(x,0,2)_for(y,0,2)update(now,m,0,x,y);
        x=y=1;
        //左右边界都在扩张 
        _rep(p,l,r)_rep(q,p,r)update(f[i-1][j-k][p][q][1][1]+now,p,q,1,1);
        x=y=0;
        //左右边界都在收缩 
        _rep(p,1,l)_rep(q,r,m)
        {
            update(f[i-1][j-k][p][q][0][0]+now,p,q,0,0);
            update(f[i-1][j-k][p][q][1][0]+now,p,q,1,0);
            update(f[i-1][j-k][p][q][0][1]+now,p,q,0,1);
            update(f[i-1][j-k][p][q][1][1]+now,p,q,1,1);
        }
        x=1,y=0;
        //左扩右缩 
        _rep(p,l,r)_rep(q,r,m)
        {
            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;
        //左缩右扩 
        _rep(p,1,l)_rep(q,l,r)
        {
            update(f[i-1][j-k][p][q][0][1]+now,p,q,0,1);
            update(f[i-1][j-k][p][q][1][1]+now,p,q,1,1);
        }
    }
    _rep(i,1,n)_rep(l,1,m)_rep(r,1,m)_for(x,0,2)_for(y,0,2)if(ans<f[i][K][l][r][x][y])ans=f[i][K][l][r][x][y],si=i,sl=l,sr=r,sx=x,sy=y;
    printf("Oil : %d\n",ans);
    print(si,K,sl,sr,sx,sy);
    return 0;
}

C++ 解法, 执行用时: 157ms, 内存消耗: 85496K, 提交时间: 2022-01-10 09:03:50

#include<bits/stdc++.h>
#define go(i,a,b)for(int i=a;i<=b;i++)
using namespace std;
int n,m,k,a,ls[20][20],f[20][226][20][20][2][2];
struct point{int l,r,x,y;}t[20][226][20][20][2][2];
int a1,a2,a3,a4,a5,a6;
void print(int a1,int a2,int a3,int a4,int a5,int a6){
    if(!a1||!a2)return;
    go(i,a3,a4)cout<<a1<<" "<<i<<"\n";
    print(a1-1,a2-(a4-a3+1),t[a1][a2][a3][a4][a5][a6].l,t[a1][a2][a3][a4][a5][a6].r,t[a1][a2][a3][a4][a5][a6].x,t[a1][a2][a3][a4][a5][a6].y);
    return;
}
int main(){
	cin>>n>>m>>k;
    go(i,1,n)go(j,1,m)cin>>ls[i][j],ls[i][j]+=ls[i][j-1];
    go(hg,1,n)go(tt,1,k)go(l,1,m)go(r,l,m){
        int ss=ls[hg][r]-ls[hg][l-1],ln=r-l+1;
        if(tt<ln)break;
        go(p,l,r)go(q,p,r)
        if(f[hg][tt][l][r][1][0]<ss+f[hg-1][tt-ln][p][q][1][0])f[hg][tt][l][r][1][0]=ss+f[hg-1][tt-ln][p][q][1][0],t[hg][tt][l][r][1][0]={p,q,1,0};
        go(p,l,r)go(q,r,m)go(y,0,1)
        if(f[hg][tt][l][r][1][1]<ss+f[hg-1][tt-ln][p][q][1][y])f[hg][tt][l][r][1][1]=ss+f[hg-1][tt-ln][p][q][1][y],t[hg][tt][l][r][1][1]={p,q,1,y};
        go(p,1,l)go(q,l,r)go(x,0,1)
        if(f[hg][tt][l][r][0][0]<ss+f[hg-1][tt-ln][p][q][x][0])f[hg][tt][l][r][0][0]=ss+f[hg-1][tt-ln][p][q][x][0],t[hg][tt][l][r][0][0]={p,q,x,0};
        go(p,1,l)go(q,r,m)go(x,0,1)go(y,0,1)
        if(f[hg][tt][l][r][0][1]<ss+f[hg-1][tt-ln][p][q][x][y])f[hg][tt][l][r][0][1]=ss+f[hg-1][tt-ln][p][q][x][y],t[hg][tt][l][r][0][1]={p,q,x,y};
        if(tt!=k)continue;
        go(x,0,1)go(y,0,1)if(a<f[hg][tt][l][r][x][y])a=f[hg][tt][l][r][x][y],a1=hg,a2=tt,a3=l,a4=r,a5=x,a6=y;
    }
    cout<<"Oil : "<<a<<"\n";
    print(a1,a2,a3,a4,a5,a6);
    return 0;
}