题解：P10972 I-Country

题目传送门

思路

因为占据的连通块的左端点先递减、后递增，右端点先递增、后递减，所以设 $f_{i,j,l,r,x(0/1),y(0/1)}$ 为前 $i$ 行中，选择 $j$ 个方格，其中第 $i$ 行选择的区间的左端点为 $l$，右端点为 $r$，$x$ 表示左端点是否出现递增，$y$ 表示右端点是否递增的所有方案的最大石油数量。

容易列出状态转移方程，
f i , j , l , r , 0 , 0 = max ⁡ { f i − 1 , j − ( r − l + 1 ) , a , b , 0 , 0 , f i − 1 , j − ( r − l + 1 ) , a , b , 0 , 1 } + s i , r − s i , l − 1 f i , j , l , r , 0 , 1 = max ⁡ { f i − 1 , j − ( r − l + 1 ) , a , b , 0 , 1 } + s i , r − s i , l − 1 f i , j , l , r , 1 , 0 = max ⁡ { f i − 1 , j − ( r − l + 1 ) , a , b , 0 , 0 , f i − 1 , j − ( r − l + 1 ) , a , b , 0 , 1 , f i − 1 , j − ( r − l + 1 ) , a , b , 1 , 0 , f i − 1 , j − ( r − l + 1 ) , a , b , 1 , 1 } + s i , r − s i , l − 1 f i , j , l , r , 1 , 1 = max ⁡ { f i − 1 , j − ( r − l + 1 ) , a , b , 0 , 1 , f i − 1 , j − ( r − l + 1 ) , a , b , 1 , 1 } + s i , r − s i , l − 1 f_{i,j,l,r,0,0}=\max\{f_{i-1,j-(r-l+1),a,b,0,0},f_{i-1,j-(r-l+1),a,b,0,1}\}+s_{i,r}-s_{i,l-1}\\ f_{i,j,l,r,0,1}=\max\{f_{i-1,j-(r-l+1),a,b,0,1}\}+s_{i,r}-s_{i,l-1}\\ f_{i,j,l,r,1,0}=\max\{f_{i-1,j-(r-l+1),a,b,0,0},f_{i-1,j-(r-l+1),a,b,0,1},f_{i-1,j-(r-l+1),a,b,1,0},f_{i-1,j-(r-l+1),a,b,1,1}\}+s_{i,r}-s_{i,l-1}\\ f_{i,j,l,r,1,1}=\max\{f_{i-1,j-(r-l+1),a,b,0,1},f_{i-1,j-(r-l+1),a,b,1,1}\}+s_{i,r}-s_{i,l-1}\\ fi,j,l,r,0,0​=max{fi−1,j−(r−l+1),a,b,0,0​,fi−1,j−(r−l+1),a,b,0,1​}+si,r​−si,l−1​fi,j,l,r,0,1​=max{fi−1,j−(r−l+1),a,b,0,1​}+si,r​−si,l−1​fi,j,l,r,1,0​=max{fi−1,j−(r−l+1),a,b,0,0​,fi−1,j−(r−l+1),a,b,0,1​,fi−1,j−(r−l+1),a,b,1,0​,fi−1,j−(r−l+1),a,b,1,1​}+si,r​−si,l−1​fi,j,l,r,1,1​=max{fi−1,j−(r−l+1),a,b,0,1​,fi−1,j−(r−l+1),a,b,1,1​}+si,r​−si,l−1​
。

注意，由于联通，所以 $r\ge a$ 且 $l\le b$。因为递增递减，所以当 $x=0$ 时，$l\le a$，当 $x=1$ 时，$l\ge a$，当 $y=0$ 时，$r\le b$，当 $y=1$ 时，$r\ge b$。$s_{i,j}$ 为第 $i$ 行的前缀和，不是二维前缀和。

最终答案为 max ⁡ { f i , k , l , r , x , y } \max\{f_{i,k,l,r,x,y}\} max{fi,k,l,r,x,y​}，输出路径可以存一个结构体 $l{a}_{i,j,l,r,x,y}$ 统计 $f_{i,j,l,r,x,y}$ 从哪里转移来。

思路容易想，代码细节却很多，本人被硬控了几个小时。

代码

//要C++14(GCC 9)，不然会RE
#include <bits/stdc++.h>
using namespace std;
const int N=25;
struct Last{int i,j,l,r,x,y;
}la[N][N*N][N][N][2][2];
int n,m,k,a[N][N],s[N][N],f[N][N*N][N][N][2][2];
int main(){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);s[i][j]=s[i][j-1]+a[i][j];}for(int i=1;i<=n;i++)for(int j=1;j<=i*m;j++)for(int l=1;l<=m;l++)for(int r=l;r<=m;r++){if(r-l+1+(i-1)*m<j || j<r-l+1)continue;int sum=s[i][r]-s[i][l-1];if(i==1){f[i][j][l][r][0][0]=f[i][j][l][r][0][1]=f[i][j][l][r][1][0]=f[i][j][l][r][1][1]=sum;continue;}//x=0,y=0for(int x=1;x<=m;x++)for(int y=x;y<=m;y++)if(!(y<l || x>r) && x>=l && y>=r){//注意要联通,l要递减,r要递减if(f[i-1][j-(r-l+1)][x][y][0][0]+sum>f[i][j][l][r][0][0])f[i][j][l][r][0][0]=f[i-1][j-(r-l+1)][x][y][0][0]+sum,la[i][j][l][r][0][0]={i-1,j-(r-l+1),x,y,0,0};if(f[i-1][j-(r-l+1)][x][y][0][1]+sum>f[i][j][l][r][0][0])f[i][j][l][r][0][0]=f[i-1][j-(r-l+1)][x][y][0][1]+sum,la[i][j][l][r][0][0]={i-1,j-(r-l+1),x,y,0,1};}//x=0,y=1for(int x=1;x<=m;x++)for(int y=x;y<=m;y++)if(!(y<l || x>r) && x>=l && y<=r){//l要递减,r要递增if(f[i-1][j-(r-l+1)][x][y][0][1]+sum>f[i][j][l][r][0][1])f[i][j][l][r][0][1]=f[i-1][j-(r-l+1)][x][y][0][1]+sum,la[i][j][l][r][0][1]={i-1,j-(r-l+1),x,y,0,1};}//x=1,y=0for(int x=1;x<=m;x++)for(int y=x;y<=m;y++)if(!(y<l || x>r) && x<=l && y>=r){//l要递增,r要递减if(f[i-1][j-(r-l+1)][x][y][0][0]+sum>f[i][j][l][r][1][0])f[i][j][l][r][1][0]=f[i-1][j-(r-l+1)][x][y][0][0]+sum,la[i][j][l][r][1][0]={i-1,j-(r-l+1),x,y,0,0};if(f[i-1][j-(r-l+1)][x][y][0][1]+sum>f[i][j][l][r][1][0])f[i][j][l][r][1][0]=f[i-1][j-(r-l+1)][x][y][0][1]+sum,la[i][j][l][r][1][0]={i-1,j-(r-l+1),x,y,0,1};if(f[i-1][j-(r-l+1)][x][y][1][0]+sum>f[i][j][l][r][1][0])f[i][j][l][r][1][0]=f[i-1][j-(r-l+1)][x][y][1][0]+sum,la[i][j][l][r][1][0]={i-1,j-(r-l+1),x,y,1,0};if(f[i-1][j-(r-l+1)][x][y][1][1]+sum>f[i][j][l][r][1][0])f[i][j][l][r][1][0]=f[i-1][j-(r-l+1)][x][y][1][1]+sum,la[i][j][l][r][1][0]={i-1,j-(r-l+1),x,y,1,1};}//x=1,y=1for(int x=1;x<=m;x++)for(int y=x;y<=m;y++)if(!(y<l || x>r) && x<=l && y<=r){//l要递增,r要递增if(f[i-1][j-(r-l+1)][x][y][0][1]+sum>f[i][j][l][r][1][1])f[i][j][l][r][1][1]=f[i-1][j-(r-l+1)][x][y][0][1]+sum,la[i][j][l][r][1][1]={i-1,j-(r-l+1),x,y,0,1};if(f[i-1][j-(r-l+1)][x][y][1][1]+sum>f[i][j][l][r][1][1])f[i][j][l][r][1][1]=f[i-1][j-(r-l+1)][x][y][1][1]+sum,la[i][j][l][r][1][1]={i-1,j-(r-l+1),x,y,1,1};}}int ans=0;Last tmp;for(int i=1;i<=n;i++)for(int l=1;l<=m;l++)for(int r=l;r<=m;r++){if(f[i][k][l][r][0][0]>ans)ans=f[i][k][l][r][0][0],tmp={i,k,l,r,0,0};//tmp存储当前的状态if(f[i][k][l][r][0][1]>ans)ans=f[i][k][l][r][0][1],tmp={i,k,l,r,0,1};if(f[i][k][l][r][1][0]>ans)ans=f[i][k][l][r][1][0],tmp={i,k,l,r,1,0};if(f[i][k][l][r][1][1]>ans)ans=f[i][k][l][r][1][1],tmp={i,k,l,r,1,1};}printf("Oil : %d",ans);while(tmp.j && tmp.i){//输出路径for(int i=tmp.l;i<=tmp.r;i++)printf("\n%d %d",tmp.i,i);tmp=la[tmp.i][tmp.j][tmp.l][tmp.r][tmp.x][tmp.y];}return 0;
}