5104 I-country
在 N*M 的矩阵中，每个格子有一个权值，要求寻找一个包含 K 个格子的凸连通块（连通块中间没有空缺，并且轮廓是凸的，如书中图片所示），使这个连通块中的格子的权值和最大。求出这个最大的权值和，并给出连通块的具体方案。本题有SPJ，输出任意一种方案即可。N,M≤15,K≤225。
- 用f[i,j,l,r,x,y]表示前i行选择了j个格子，其中第i行选择了第l到第r个格子(若不选则均为0)，左边界的单调类型为X,右边界的单调类型为y（0表示递增，1表示递减）时，能构成的凸联通快的最大权值和。
- 状态转移：借用大佬博客：
-
1.左边界列号递减，右边界列号递增（两边界都处于扩张状态）
f[i,j,l,r,1,0] = A[i][r]-A[i][l] + max{f[i-1,j-(r-l+1),p,q,1,0]};//j>r-l+1>0
= A[i][r]-A[i][l] + max{f[i-1,0,0,0,1,0]};//j=r-l+1>0
2.左右边界列号都递减（左边界扩张，右边界收缩）
f[i,j,l,r,1,1] = A[i][r]-A[i][l] + max{max{f[i-1,j-(r-l+1),p,q,1,y]}(0<=y<=1)}
3.左右边界列号都递减（左边界收缩，右边界扩张）
f[i,j,l,r,0,0] = A[i][r]-A[i][l] + max{{f[i-1,j-(r-l+1),p,q,x,0](0<=x<=1)}}
4.左边界列号递增，右边界列号递减（两边界都处于收缩状态）
f[i,j,l,r,0,1] = A[i][r]-A[i][l] + max{max{max{f[i-1,j-(r-l+1),p,q,x,y]}(0<=y<=1)}(0<=x<=1)}(p<=l<=r<=q)
对于2,3,4的max嵌套max，可能有点难以理解
我们来想一下，我们要进行收缩，那么我们这个收缩的状态是怎么得来的?
答：由上一行扩张或收缩而来
所以当收缩右边界时，我们先比较的是上一行右边界标记扩张和右边界标记收缩的最大值，再和当前行比较
左边界收缩时同理。
这样我们就能推出2和3。
进而我们想4这种情况。
左右边界同时进行收缩，我们就要嵌套3次，先由上述确定右边界状态，再由已确定右边界状态来确定左边界状态，最后由已确定的左边界状态和右边界状态来确定当前行
//此处状态单指标记为收缩或扩张，即上一行的左/右边界由上上一行的左/右边界扩张或收缩得到本题还要求输出方案。
在动态规划需要给出方案时，通常做法是额外使用一些与DP状态大小相同的数组记录下来每个状态，通过递归返回最初的状态，然后逐层退出的同时输出方案代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <cctype> 4 5 template <typename T> 6 inline T max(T a,T b){ 7 return a>b ? a : b; 8 } 9 template <typename T> 10 inline T min(T a,T b){ 11 return a<b ? a : b; 12 } 13 template <typename T> 14 inline void read(T &x) 15 { 16 x=0; 17 int p=1; char ch=getchar(); 18 while(!isdigit(ch)&&ch!='-') if(ch=='-') p=-1,ch=getchar(); 19 20 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch-'0'),ch=getchar(); 21 x=p*x; 22 } 23 24 int n,m,k; 25 int a[20][20]; 26 int sum[20][20]; 27 int i,j,l,r,x,y; 28 int f[21][230][20][20][2][2]; 29 struct method{ 30 int l,r,x,y; 31 }met[21][230][20][20][2][2]; 32 33 inline void update(int dat,int nl,int nr,int nx,int ny) 34 { 35 int &a=f[i][j][l][r][x][y]; 36 if(dat<=a) return ; 37 method &p=met[i][j][l][r][x][y]; 38 a=dat; 39 p=method{nl,nr,nx,ny}; 40 } 41 42 void print(int i,int j,int l,int r,int x,int y) 43 { 44 if(j<=0) return; 45 method &p=met[i][j][l][r][x][y]; 46 // printf("%d ",j); 47 print(i-1,j-(r-l+1),p.l,p.r,p.x,p.y); 48 49 for(int s=l ; s<=r ; s++) 50 printf("%d %d ",i,s); 51 } 52 int main() 53 { 54 scanf("%d%d%d",&n,&m,&k); 55 for(i=1 ; i<=n ; i++) 56 for(j=1 ; j<=m ; j++) scanf("%d",&a[i][j]),sum[i][j]=sum[i][j-1]+a[i][j]; 57 58 for(i=1 ; i<=n ; i++) 59 for(j=1 ; j<=k ; j++) 60 for(l=1 ; l<=m ; l++) 61 for(r=l ; r<=m ; r++) 62 { 63 int t=r-l+1; 64 int now=sum[i][r]-sum[i][l-1]; 65 if(t>j) break; 66 //左减右增 67 x=1,y=0; 68 for(int p=l ; p<=r ; p++) 69 for(int q=p ; q<=r ; q++) 70 { 71 update(f[i-1][j-t][p][q][1][0]+now,p,q,1,0); 72 } 73 //左减右减 74 x=1,y=1; 75 for(int p=l ; p<=r ; p++) 76 for(int q=r ; q<=m ; q++) 77 { 78 update(f[i-1][j-t][p][q][1][1]+now,p,q,1,1); 79 update(f[i-1][j-t][p][q][1][0]+now,p,q,1,0); 80 } 81 //左增右增 82 x=0,y=0; 83 for(int p=1 ; p<=l ; p++) 84 for(int q=l ; q<=r ; q++) 85 { 86 update(f[i-1][j-t][p][q][1][0]+now,p,q,1,0); 87 update(f[i-1][j-t][p][q][0][0]+now,p,q,0,0); 88 } 89 //左增右减 90 x=0,y=1; 91 for(int p=1 ; p<=l ; p++) 92 for(int q=r ; q<=m ; q++) 93 { 94 update(f[i-1][j-t][p][q][1][0]+now,p,q,1,0); 95 update(f[i-1][j-t][p][q][1][1]+now,p,q,1,1); 96 update(f[i-1][j-t][p][q][0][1]+now,p,q,0,1); 97 update(f[i-1][j-t][p][q][0][0]+now,p,q,0,0); 98 } 99 } 100 int ans=0; 101 int ai,al,ar,ax,ay; 102 for(i=1 ; i<=n ; i++) 103 for(l=1 ; l<=m ; l++) 104 for(r=l ; r<=m ; r++) 105 for(x=0 ; x<=1 ; x++) 106 for(y=0 ; y<=1 ; y++) 107 { 108 if(f[i][k][l][r][x][y]>ans) 109 { 110 ans=f[i][k][l][r][x][y]; 111 ai=i,al=l,ar=r,ax=x,ay=y; 112 } 113 } 114 printf("Oil : %d ",ans); 115 print(ai,k,al,ar,ax,ay); 116 return 0; 117 }