I-country

2024-03-02 17:17:10

首先在说这道题前，我要感谢

shellpicker

大佬的题解，链接如下：https://www.cnblogs.com/wzj-xhjbk/p/9790976.html

题目描述

在N×MN×M的矩阵中，每个格子有一个权值，要求寻找一个包含K个格子的凸连通块（连通块中间没有空缺，并且轮廓是凸的，如右图所示），使这个连通块中的格子的权值和最大。求出这个最大的权值和，并给出连通块的具体方案。

输入格式

在输入的第一行上有3个整数N，M，K（1 <= N，M <= 15,0 <= K <= N * M）。接下来的N行包含M个整数，它们是该正方形上的石油资源数量。这些数字中的每一个都在0到1000的范围内。

输出格式

在输出的第一行，写入字符串“Oil：X”，其中整数X是可由A国控制的最大油数。接下来你应该输出K对数字---将被A国占据的正方形坐标。第一个坐标是行数（从上到下，从1开始），第二个是列数（从左到右，从1开始）。

样例数据

input

2 3 4 
10 20 30 
40 2 3

output

数据规模与约定

时间限制：0.75s0.75s

空间限制：65MB

题解：

　　首先我们得先了解一下“凸连通块”的概念，算阶上解释为：可以划分成连续的若干行，每行的左端点列号先递减，后递增，右端点先递增，后递减。为了方便理解，如图所示：

像这样的图形，称之为凸连通块，以下简称块，当然，块通常不可能是对称的（这是句废话）。

我们从块的最下面往上看，如箭头所指方向，除第一行外，每个第i行的状态只与第i-1行有关。知道这个前提，接下来我们来详细说明一下状态转移。

首先我们设dp[i][j][l][r][x][y],含义为：前i行选择了j块，其中第i行块最左为l，最右为r，x（0 / 1）左边单调性：0为递增，1为递减，y同理。状态则只有四种。 1，0 1，1 0，1 0，0

1. 1，0 左边递减，右边递增

i-1行状态也必然为1，0观察块的概念图即可得。

2.1，1左右均递减

与黄线交点即为i-1的状态由两图可得。第i-1行的状态可能为1，1或1，0。

3.0，1

与黄线交点即为i-1的状态

由这四个图可得i-1行状态为1.0或1，1或0，1或0，0.。

4.0，0

与黄线交点即为i-1的状态由两图可得，第i-1行有1，0或0，0两种状态。

分析结束，代码具体如下（含解析）：

#include<bits/stdc++.h>
using namespace std;

#define f(i,a,b) for(i = a;i <= b;i ++)//减少大量for循环
int i,j,p,l,r,q,x,y;//循环变量
int ii,ll,rr,xx,yy,ans;
const int N = 26;    
int n,m,k,sum[20][20],dp[N][N*N][N][N][2][2];//前i行选择了j块，其中第i行块最左为l，最右为r，x（0 / 1）左边单调性：0为递增，1为递减，y同理
struct edge
{
    int l,r,x,y;
}pp[N][N*N][N][N][2][2];//记录方案数

void check(int NUM,int L,int R,int X,int Y)
{
    edge& P = pp[i][j][l][r][x][y];
    if(dp[i][j][l][r][x][y] >= NUM) return;
    dp[i][j][l][r][x][y] = NUM;
    P = (edge){L,R,X,Y}; 
}//状态转移（比大小，赋值）

void print(int i,int j,int l,int r,int x,int y)
{
    if(j == 0) return;//记忆化搜索
    edge& P = pp[i][j][l][r][x][y];
    print(i - 1,j - r + l - 1,P.l,P.r,P.x,P.y);
    f(j,l,r) printf("%d %d\n",i,j); 
}//将所有方案打印

int main()
{
//    freopen("input.in","r",stdin);
//    freopen("output.out","w",stdout); 
    cin >> n >> m >> k;
    f(i,1,n)f(j,1,m)
    {
        scanf("%d",&sum[i][j]);
        sum[i][j] += sum[i][j-1];
    }//提前求出前缀和，方便计算
    f(i,1,n)f(j,1,k)f(l,1,m)f(r,l,m)
    {
        if(r - l + 1 > j) break;//r-l+1如果小于j，无意义，退出
//四种分类讨论，在计算时也可以将r-l+1设为一个值，求块数，并有利于计算，我到最后才发现，还可以省很多，代码可以更简洁
        x = y = 1;//① 
        int num = sum[i][r] - sum[i][l - 1];//方便计算
        f(p,l,r)f(q,r,m)
        { 
            check(dp[i - 1][j - r + l - 1][p][q][1][0] + num,p,q,1,0);
            check(dp[i - 1][j - r + l - 1][p][q][1][1] + num,p,q,1,1);
        }
        x = 1,y = 0;//②
        f(p,l,r)f(q,p,r)
            check(dp[i - 1][j - r + l - 1][p][q][1][0] + num,p,q,1,0);
        x = 0,y = 1;//③ 
        f(p,1,l)f(q,r,m)
        {
            check(dp[i - 1][j - r + l - 1][p][q][1][1] + num,p,q,1,1);
            check(dp[i - 1][j - r + l - 1][p][q][1][0] + num,p,q,1,0);
            check(dp[i - 1][j - r + l - 1][p][q][0][1] + num,p,q,0,1);
            check(dp[i - 1][j - r + l - 1][p][q][0][0] + num,p,q,0,0);
        }
        x = y = 0;//④ 
        f(p,1,l)f(q,l,r)
        {
            check(dp[i - 1][j -  r + l - 1][p][q][1][0] + num,p,q,1,0);
            check(dp[i - 1][j -  r + l - 1][p][q][0][0] + num,p,q,0,0);
        }    
    }
    f(i,1,n)f(l,1,m)f(r,l,m)f(x,0,1)f(y,0,1)
        if(ans < dp[i][k][l][r][x][y])
        {
            ans = dp[i][k][l][r][x][y];
            ii = i,ll = l,rr = r,xx = x,yy = y;
        }
        printf("Oil : %d\n",ans);
        print(ii,k,ll,rr,xx,yy);
    return 0;
}

　　这道题也结束，总结一下学到了什么。还要感谢shellpicker大佬，在看到他的题解前我只会很“耿直”的写代码，以至于第一次，我写了一个120多行的dp，后来一改快一二百行，几十个循环差错查了一个多小时后放弃了。但看了大佬的题解后，恍然大悟，使自己

代码更简洁，发现宏定义原来这么好用，省略了许多循环（菜鸟勿喷），还有就是“&”引用也省略了许多代码量，减至77行。

　　❀完结撒花❀

码农公寓