题解：P10972 I-Country
题目传送门
思路
因为占据的连通块的左端点先递减、后递增，右端点先递增、后递减，所以设 f i , j , l , r , x ( 0 / 1 ) , y ( 0 / 1 ) f_{i,j,l,r,x(0/1),y(0/1)} fi,j,l,r,x(0/1),y(0/1) 为前 i i i 行中，选择 j j j 个方格，其中第 i i i 行选择的区间的左端点为 l l l，右端点为 r r r， x x x 表示左端点是否出现递增， y y 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−1fi,j,l,r,0,1=max{fi−1,j−(r−l+1),a,b,0,1}+si,r−si,l−1fi,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−1fi,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 ≥ a r\ge a r≥a 且 l ≤ b l\le b l≤b。因为递增递减，所以当 x = 0 x=0 x=0 时， l ≤ a l\le a l≤a，当 x = 1 x=1 x=1 时， l ≥ a l\ge a l≥a，当 y = 0 y=0 y=0 时， r ≤ b r\le b r≤b，当 y = 1 y=1 y=1 时， r ≥ b r\ge b r≥b。 s i , j s_{i,j} si,j 为第 i i 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 la_{i,j,l,r,x,y} lai,j,l,r,x,y 统计 f i , j , l , r , x , y f_{i,j,l,r,x,y} fi,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=0
for(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=1
for(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=0
for(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=1
for(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;
}