Acwing 276 I-Country（线性dp）
题意描述
在\(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 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 PII;
typedef pair PCC;
typedef pair PDD;
typedef pair PLL;
typedef pair PIII;
typedef pair 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>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