5104 I-country

客官°小女子只卖身不卖艺 2022-01-07 16:25 193阅读 0赞

## [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表示递减）时，能构成的凸联通快的最大权值和。
 *  状态转移：借用**[大佬博客][Link 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状态大小相同的数组记录下来每个状态，通过递归返回最初的状态，然后逐层退出的同时输出方案
    
    **代码：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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\n",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\n",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\n",ans);
    115     print(ai,k,al,ar,ax,ay);
    116     return 0;
    117 }

转载于:https://www.cnblogs.com/wmq12138/p/10366663.html

[5104 I-country]: http://contest-hunter.org:83/contest/0x50%E3%80%8C%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E3%80%8D%E4%BE%8B%E9%A2%98/5104%20I-country
[Link 1]: https://www.cnblogs.com/ywjblog/p/9744362.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/7a86ff4763f1402d806894a4165c142f.png

5104 I-country

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 HDU5104-Primes Problem

相关 5104 I-country

相关 bzoj5104 Fib数列（BSGS+二次剩余）