$CH5104\ I-country$ 线性$DP$

Sol

”凸联通块“是什么意思呢？

其实就是图形的左端点先减小再增大，右端点先增大再减小

阶段

考虑到第k行,已经选了i个格子

状态

1.第i行的左端点与右端点

2.这一行的左端点相对于上一行的左端点是递增还是递减

这一行的右端点相对于上一行的右端点是递增还是递减

所以，f[k][i][l][r][0/1][0/1]表示考虑完第k行,已经选了i个格子,这一行的左端点是l,右端点是r,左端点相对于上一行递增(0)/递减(1),这一行的右端点.......

转移

考虑p,q的范围以及通过上一行的四种状态的哪种转移而来

有这么四种情况：(p,q为枚举的上一行的左右端点)

1.左减右增

l<=p<=q<=r<=m 通过f[k][i][p][q][1][0]转移

2.左增右增

1<=p<=l<=q<=r<=m 通过f[k][i][p][q][0/1][0]转移

3.左减右减

l<=p<=r<=q<=m 通过f[k][i][p][q][1][0/1]转移

4.左增右减

1<=p<=l<=r<=q<=m 通过f[k][i][p][q][0/1][0/1]转移

Code

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define Rg register

 #define il inline

 #define go(i,a,b) for(Rg int i=a;i<=b;i++)

 using namespace std;

 int ans,n,m,K,ak,ai,al,ar,ax,ay,c[][],f[][][][][][];

 struct node{int l,r,x,y;}a[][][][][][];

 il void print(int k,int i,int l,int r,int x,int y)

 {

     if(!k || !i)return;

     print(k-,i-(r-l+),a[k][i][l][r][x][y].l,a[k][i][l][r][x][y].r,a[k][i][l][r][x][y].x,a[k][i][l][r][x][y].y);

     go(t,l,r)printf("%d %d\n",k,t);

 }

 int main()

 {

     freopen("CH5104.out","w",stdout);

     scanf("%d%d%d",&n,&m,&K);

     go(i,,n)go(j,,m)scanf("%d",&c[i][j]),c[i][j]+=c[i][j-];

     go(k,,n)

         go(i,,K)

         go(l,,m)

         go(r,l,m)

     {

         int sm=c[k][r]-c[k][l-],t=r-l+;

         if(i<t)break;

         //1,0 zuojian youzen

             go(p,l,r)go(q,p,r)

                 if(f[k][i][l][r][][]<sm+f[k-][i-t][p][q][][])

                     f[k][i][l][r][][]=sm+f[k-][i-t][p][q][][],a[k][i][l][r][][]=(node){p,q,,};

         //1,1 zuojian youjian

         go(p,l,r)go(q,r,m)go(y,,)

             if(f[k][i][l][r][][]<sm+f[k-][i-t][p][q][][y])

                 f[k][i][l][r][][]=sm+f[k-][i-t][p][q][][y],a[k][i][l][r][][]=(node){p,q,,y};

         //0,1 zuozen youjian

         go(p,,l)go(q,r,m)go(x,,)go(y,,)

             if(f[k][i][l][r][][]<sm+f[k-][i-t][p][q][x][y])

                 f[k][i][l][r][][]=sm+f[k-][i-t][p][q][x][y],a[k][i][l][r][][]=(node){p,q,x,y};

         //0,0 zuozen youzen

         go(p,,l)go(q,l,r)go(x,,)

             if(f[k][i][l][r][][]<sm+f[k-][i-t][p][q][x][])

                 f[k][i][l][r][][]=sm+f[k-][i-t][p][q][x][],a[k][i][l][r][][]=(node){p,q,x,};

         if(i!=K)continue;

         go(x,,)go(y,,)

             if(ans<f[k][i][l][r][x][y]){ans=f[k][i][l][r][x][y];ak=k;ai=i;al=l;ar=r;ax=x;ay=y;}

     }

     printf("Oil : %d\n",ans);

     print(ak,ai,al,ar,ax,ay);

     return ;

 }

巴特西

$CH5104\ I-country$ 线性$DP$

最新文章

热门文章