• 周一. 5月 27th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

HDU3377 Plan

admin

11月 28, 2021

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3377


简单路径要求权值最大,那么为了回避括号序列单独插头的情况特判多,考虑使用最小表示法。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<vector>
  5 #include<cstdlib>
  6 #include<cmath>
  7 #include<cstring>
  8 using namespace std;
  9 #define maxn 21
 10 #define inf ((0x7fffffff)-1)
 11 #define llg int
 12 #define sizee 233
 13 #define maxnZT ((1<<20)+1)
 14 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
 15 llg n,m,code[maxn],zt[2][maxnZT],v[2][maxnZT],g[110][110],size[2],now,ne,ans=inf*-1;
 16 llg maze[10][10],val[10][10],ch[22];
 17 void outcode(llg x){for (llg i=0;i<=m;i++) code[i]=x&3,x>>=2;}
 18 
 19 struct node
 20 {
 21     llg x,val,pos;
 22 };
 23 
 24 vector<node>a[2][sizee];
 25 
 26 void decode(llg x) {for (llg i=0;i<=m;i++) code[i]=x&7,x>>=3;}
 27 
 28 void encode(llg p,llg val)
 29 {
 30     for (llg i=0;i<=20;i++) ch[i]=-1;
 31     ch[0]=0;
 32     llg C=0;
 33     for (llg i=0;i<=m;i++)
 34     {
 35         if (ch[code[i]]==-1) ch[code[i]]=++C;
 36         code[i]=ch[code[i]];
 37     }
 38     llg x=0;
 39     for (llg i=0;i<=m;i++) x+=code[i]*(1<<(i*3));
 40     llg wz=x%sizee,E=a[p][wz].size();
 41     for (llg i=0;i<E;i++)
 42         if (a[p][wz][i].x==x)
 43         {
 44             a[p][wz][i].val=max(a[p][wz][i].val,val);
 45             v[p][a[p][wz][i].pos]=max(v[p][a[p][wz][i].pos],val);
 46             return ;
 47         }
 48     size[p]++;
 49     node NEW; NEW.x=x; NEW.val=val; NEW.pos=size[p];
 50     a[p][wz].push_back(NEW);
 51     zt[p][size[p]]=x; v[p][size[p]]=val;
 52 }
 53 
 54 void init_a(llg p){for (llg i=0;i<sizee;i++) a[p][i].clear(); size[p]=0;}
 55 
 56 
 57 void shift()///换行 移位
 58 {
 59     for(int i=m;i>0;i--)
 60         code[i]=code[i-1];
 61     code[0]=0;
 62 }
 63 
 64 
 65 void dp(llg x,llg y)
 66 {
 67     llg left,up,V;
 68     for (llg K=1;K<=size[now];K++)
 69     {
 70         decode(zt[now][K]);
 71         left=code[y-1],up=code[y];//左上插头
 72         V=v[now][K];
 73 //------------------------------------------------------------
 74         if ((x==1 && y==1))//开始位置
 75         {
 76             if (maze[x][y+1])//往左走
 77             {
 78                 code[y]=17,code[y-1]=0;
 79                 encode(ne,V+val[x][y]);
 80             }
 81             if (maze[x+1][y])//往下走
 82             {
 83                 code[y-1]=17,code[y]=0;
 84                 encode(ne,V+val[x][y]);
 85             }
 86             continue;
 87         }
 88 //------------------------------------------------------------
 89         if (x==n && y==m)//结束位置
 90         {
 91             if ((!left && up) || (left && !up))//必须有且仅有一个插头
 92             {
 93                 code[y]=code[y-1]=0;
 94                 bool pd=true;
 95                 for (llg t=0;t<=m;t++) if (code[t]) pd=false;
 96                 if (pd) ans=max(ans,V+val[x][y]);
 97             }
 98             continue;
 99         }
100 //------------------------------------------------------------
101         if (left && up)//插头合并
102         {
103             if (left!=up)//如果属于同一个连通块则非法(因为形成了环)
104             {
105                 code[y]=code[y-1]=0;
106                 for (llg t=0;t<=m;t++) if (code[t]==up) code[t]=left;
107                 if (y==m) shift();
108                 encode(ne,V+val[x][y]);
109             }
110             continue;
111         }
112 //------------------------------------------------------------
113         if (left || up)//延续原来的连通分量
114         {
115             llg tmp;
116             if (left) tmp=left;else tmp=up;
117             if (maze[x][y+1])
118             {
119                 code[y-1]=0,code[y]=tmp;
120                 encode(ne,V+val[x][y]);
121             }
122             if (maze[x+1][y])
123             {
124                 code[y-1]=tmp,code[y]=0;
125                 if (y==m) shift();
126                 encode(ne,V+val[x][y]);
127             }
128         }
129 //------------------------------------------------------------
130         if (!left && !up)//没有插头,新建连通分量或者不走这一个格子
131         {
132             if (maze[x][y+1] && maze[x+1][y])
133             {
134                 code[y]=code[y-1]=17;
135                 encode(ne,V+val[x][y]);
136             }
137             code[y]=code[y-1]=0;
138             if (y==m) shift();
139             encode(ne,V);
140         }
141     }
142 }
143 
144 void work()
145 {
146     now=0,ne=0;
147     encode(now,0);
148     for (llg i=1;i<=n;i++)
149     {
150         for (llg j=1;j<=m;j++)
151         {
152             ne=now^1;
153             init_a(ne);
154             dp(i,j);
155             now=ne;
156         }
157     }
158 }
159 
160 void init()
161 {
162     memset(maze,0,sizeof(maze));
163     for (llg i=1;i<=n;i++) 
164         for (llg j=1;j<=m;j++)
165             scanf("%d",&val[i][j]),maze[i][j]=1;
166 }
167 
168 int main()
169 {
170     yyj("hdu3377");
171     llg cas=0;
172     while (scanf("%d%d",&n,&m)!=EOF)
173     {
174         ans=inf*-1;
175         cas++;
176         init();
177         if (n==1 && m==1) 
178         {
179             printf("Case %d: %d
",cas,val[n][m]);
180             init_a(1),init_a(0);
181             continue;
182         }
183         work();
184         printf("Case %d: %d
",cas,ans);
185         init_a(1),init_a(0);
186     }
187     return 0;
188 }

《HDU3377 Plan》有2个想法
  1. Wow, wonderful weblog structure! How long have you
    ever been running a blog for? you made blogging glance easy.
    The full look of your site is fantastic, let alone the content
    material! You can see similar here sklep internetowy

  2. We stumbled over here different website and thought I should check things out.
    I like what I see so now i’m following you. Look forward to looking at
    your web page for a second time. I saw similar here:
    Sklep internetowy

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注