WC2008游览计划（BZOJ2595）-白红宇

WC2008游览计划（BZOJ2595）

阅读量：6148 次

发布时间：2019-06-21

本文共 3186 字，大约阅读时间需要 10 分钟。

2595: [Wc2008]游览计划

Time Limit: 10 Sec Memory Limit: 256 MBSec Special Judge

[][]

Description

Input

第一行有两个整数，N和 M，描述方块的数目。

接下来 N行，每行有 M 个非负整数，如果该整数为 0，则该方块为一个景点；

否则表示控制该方块至少需要的志愿者数目。相邻的整数用（若干个）空格隔开，

行首行末也可能有多余的空格。

Output

由 N + 1行组成。第一行为一个整数，表示你所给出的方案

中安排的志愿者总数目。

接下来 N行，每行M 个字符，描述方案中相应方块的情况：

z ‘_’（下划线）表示该方块没有安排志愿者；

z ‘o’（小写英文字母o）表示该方块安排了志愿者；

z ‘x’（小写英文字母x）表示该方块是一个景点；

注：请注意输出格式要求，如果缺少某一行或者某一行的字符数目和要求不

一致（任何一行中，多余的空格都不允许出现），都可能导致该测试点不得分。

Sample Input

4 4

0 1 1 0

2 5 5 1

1 5 5 1

0 1 1 0

Sample Output

xoox

___o

xoox

HINT

对于100%的数据，N,M,K≤10，其中K为景点的数目。输入的所有整数均在[0,2^16]的范围内

Source

出题者XXOO的真丧病-_-#

写了好长时间了。。比较简单的插头dp。。保存路径也比较简单。。WA了N次是因为。。我把X、O写倒了。。

轮廓线以上的格子表示有没有选中，那么对于一个非景点格子，如果可以不选，那么要么是i-1,j不选，要么是i-1,j选了但是轮廓线上存在其他的格子和i-1,j是一个联通块。

Codes:

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 using namespace std; 9 const int N = 1<<15; 10 const int Hash = 10007; 11 #define nxt (cur^1) 12 #define For(i,n) for(int i=1;i<=n;i++) 13 #define Rep(i,l,r) for(int i=l;i<=r;i++) 14 #define Down(i,r,l) for(int i=r;i>=l;i--) 15 16 pair< pair
             
               ,int > opt[N*110]; 17 int pre[N*110],optot; 18 int loc,cur,n,m,maze[15][15],ans=1<<30,code[15]; 19 char Ans[15][15]; 20 21 struct statedp{ 22 int Loc[N],size,f[N],head[Hash],next[N],st[N]; 23 void clear(){size=0;memset(head,-1,sizeof(head));} 24 void push(int state,int ans,int last,int x,int y,int kind){ 25 int Key = state % Hash; 26 for(int p=head[Key];p!=-1;p=next[p]) 27 if(st[p]==state) { 28 if(ans
              
               >=3; 50 } 51 52 int encode(){ 53 int st=0,cnt=1,h[10]; 54 memset(h,-1,sizeof(h)); 55 h[0]=0; 56 Down(i,m,1){ 57 if(h[code[i]]==-1) h[code[i]]=cnt++; 58 code[i]=h[code[i]]; 59 st = (st<<3)|code[i]; 60 } 61 return st; 62 } 63 64 void trans(int Left,int Up){ 65 For(i,m) 66 if(code[i]==Up) code[i] = Left;//合并联通快 67 } 68 69 void dpblank(int i,int j,int cur,int kind){ 70 Rep(k,0,dp[cur].size-1){ 71 decode(dp[cur].st[k]); 72 int Left = (j==1)?(0):(code[j-1]) ,Up = (i==1)?(0):(code[j]),cnt=0; 73 if(kind){ 74 int tot = 0; 75 For(scan,m) tot+=(code[scan]==Up); 76 if(tot>1 || !code[j]){ 77 int tmp = code[j];code[j] = 0; 78 dp[nxt].push(encode(),dp[cur].f[k],dp[cur].Loc[k],i,j,0); 79 code[j]=tmp; 80 } 81 } 82 if(Left&&Up) trans(Left,Up);else 83 if(Left||Up) code[j] = Left + Up; 84 else code[j] = (5+(cnt++)); 85 dp[nxt].push(encode(),dp[cur].f[k]+kind,dp[cur].Loc[k],i,j,1); 86 } 87 } 88 void DP(){ 89 int cur=0;dp[cur].clear();dp[cur].push(0,0,0,0,0,0); 90 For(i,n) 91 For(j,m){ 92 dp[nxt].clear(); 93 dpblank(i,j,cur,maze[i][j]); 94 cur^=1; 95 } 96 Rep(k,0,dp[cur].size-1){ 97 decode(dp[cur].st[k]); 98 int i;for(i=1;i<=m;i++) if(code[i]>1) break; 99 if(i
               
                ,int> T = opt[i];111 int x=T.first.first,y=T.first.second,c=T.second;112 if(!maze[x][y]) Ans[x][y]='x';113 else if(c==0) Ans[x][y]='_';114 else Ans[x][y]='o';115 i=pre[i];116 }117 }118 119 int main(){120 init();121 DP();122 PrintPath(loc);123 For(i,n)124 For(j,m)125 if(j==m) printf("%c\n",Ans[i][j]);126 else printf("%c",Ans[i][j]);127 return 0;128 }