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状态大小相同的数组记录下来每个状态，通过递归返回最初的状态，然后逐层退出的同时输出方案

代码：

 #include <cstdio>

 #include <cstring>

 #include <cctype>

 template <typename T>

 inline T max(T a,T b){

     return a>b ? a : b;

 }

 template <typename T>

 inline T min(T a,T b){

     return a<b ? a : b;

 }

 template <typename T>

 inline void read(T &x)

 {

     x=;

     int p=; char ch=getchar();

     while(!isdigit(ch)&&ch!='-') if(ch=='-') p=-,ch=getchar();

     while(isdigit(ch)) x=(x<<)+(x<<)+(ch-''),ch=getchar();

     x=p*x;

 }

 int n,m,k;

 int a[][];

 int sum[][];

 int i,j,l,r,x,y;

 int f[][][][][][];

 struct method{

     int l,r,x,y;

 }met[][][][][][];

 inline void update(int dat,int nl,int nr,int nx,int ny)

 {

     int &a=f[i][j][l][r][x][y];

     if(dat<=a) return ;

     method &p=met[i][j][l][r][x][y];

     a=dat;

     p=method{nl,nr,nx,ny};

 }

 void print(int i,int j,int l,int r,int x,int y)

 {

     if(j<=) return;

     method &p=met[i][j][l][r][x][y];

 //    printf("%d\n",j);

     print(i-,j-(r-l+),p.l,p.r,p.x,p.y);

     for(int s=l ; s<=r ; s++)

         printf("%d %d\n",i,s);

 }

 int main()

 {

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

     for(i= ; i<=n ; i++)

         for(j= ; j<=m ; j++) scanf("%d",&a[i][j]),sum[i][j]=sum[i][j-]+a[i][j];

     for(i= ; i<=n ; i++)

     for(j= ; j<=k ; j++)

     for(l= ; l<=m ; l++)

     for(r=l ; r<=m ; r++)

     {

         int t=r-l+;

         int now=sum[i][r]-sum[i][l-];

         if(t>j) break;

         //左减右增

         x=,y=;

         for(int p=l ; p<=r ; p++)

           for(int q=p ; q<=r ; q++)

               {

                   update(f[i-][j-t][p][q][][]+now,p,q,,);

               }

         //左减右减

         x=,y=;

         for(int p=l ; p<=r ; p++)

           for(int q=r ; q<=m ; q++)

           {

               update(f[i-][j-t][p][q][][]+now,p,q,,);

               update(f[i-][j-t][p][q][][]+now,p,q,,);

           }

         //左增右增

         x=,y=;

         for(int p= ; p<=l ; p++)

           for(int q=l ; q<=r ; q++)

           {

               update(f[i-][j-t][p][q][][]+now,p,q,,);

               update(f[i-][j-t][p][q][][]+now,p,q,,);

           }

         //左增右减

         x=,y=;

         for(int p= ; p<=l ; p++)

           for(int q=r ; q<=m ; q++)

           {

               update(f[i-][j-t][p][q][][]+now,p,q,,);

               update(f[i-][j-t][p][q][][]+now,p,q,,);

               update(f[i-][j-t][p][q][][]+now,p,q,,);

               update(f[i-][j-t][p][q][][]+now,p,q,,);

           }

     }

     int ans=;

     int ai,al,ar,ax,ay;

     for(i= ; i<=n ; i++)

      for(l= ; l<=m ; l++)

        for(r=l ; r<=m ; r++)

          for(x= ; x<= ; x++)

            for(y= ; y<= ; y++)

            {

                 if(f[i][k][l][r][x][y]>ans)

                 {

                   ans=f[i][k][l][r][x][y];

                   ai=i,al=l,ar=r,ax=x,ay=y;

                 }

            }

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

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

     return ;

 }

巴特西

5104 I-country

5104 I-country

最新文章

热门文章