【插头DP】hdu1964-Pipes

【题目大意】

给出一个网格，经过边要付出代价。求走过每一个格子的欧拉回路的最小代价。
【思路】

裸裸的插头DP~然而写了好久orz

【错误点】

整个人跟制杖了一样QAQ

hash实力写挂…m和n搞反了。具体看注释。

  1 #include<bits/stdc++.h>
  2 #define u 0
  3 #define d 1
  4 #define l 2
  5 #define r 3
  6 using namespace std;
  7 typedef long long ll;
  8 const int MAXN=15;
  9 const int HASH=10007;
 10 struct Hashmap
 11 {
 12     vector<int> hash[HASH];
 13     vector<ll> state,f;
 14     void clear()
 15     {
 16         for (int i=0;i<HASH;i++) vector<int>().swap(hash[i]);
 17         vector<ll>().swap(state);
 18         vector<ll>().swap(f);
 19     }
 20     
 21     void push(ll st,ll ans)
 22     {
 23         int now=st%HASH;
 24         for (int i=0;i<hash[now].size();i++)
 25         {
 26             int h=hash[now][i];
 27             if (state[h]==st) //st写成了now QAQ下面return还忘记写到大括号里面去了，浪费了3个小时查orz 
 28             {
 29                 f[h]=min(f[h],ans);
 30                 return;
 31             }
 32         }
 33         hash[now].push_back(state.size());
 34         state.push_back(st);
 35         f.push_back(ans);
 36     }
 37 }dp[2];
 38 int m,n;
 39 int maze[MAXN][MAXN][4],code[MAXN];//上下左右 
 40 int ch[MAXN];
 41 
 42 void decode(ll st)
 43 {
 44     for (int i=n;i>=0;i--)
 45     {
 46         code[i]=st&7;
 47         st>>=3;
 48     }
 49 }
 50 
 51 ll encode()
 52 {
 53     ll ret=0;
 54     int cnt=0;
 55     memset(ch,-1,sizeof(ch));
 56     ch[0]=0;
 57     for (int i=0;i<=n;i++)
 58     {
 59         if (ch[code[i]]==-1) ch[code[i]]=++cnt;
 60         code[i]=ch[code[i]];
 61         ret<<=3;
 62         ret+=code[i];
 63     }
 64     return ret;
 65 }
 66 
 67 void shift()
 68 {
 69     for (int i=n;i>0;i--) code[i]=code[i-1];
 70     code[0]=0;
 71 } 
 72 
 73 void dpblank(int i,int j,int cur)
 74 {
 75     for (int k=0;k<dp[1-cur].state.size();k++)
 76     {
 77         decode(dp[1-cur].state[k]);
 78         if (j==1)
 79         {
 80             if (code[n]!=0) continue;
 81                 else shift();
 82         }
 83         int left=code[j-1],up=code[j];//left和up要等到shift之后再取值 
 84         if (left && up)
 85         {
 86             if (left==up)
 87             {
 88                 if (i==m && j==n)
 89                 {
 90                     code[j-1]=code[j]=0;
 91                     dp[cur].push(encode(),dp[1-cur].f[k]);
 92                 }
 93             }
 94             else
 95             {
 96                 code[j-1]=code[j]=0;
 97                 for (int i=0;i<=n;i++) if (code[i]==left) code[i]=up;
 98                 dp[cur].push(encode(),dp[1-cur].f[k]);
 99             }
100         }
101         
102         if ((left && !up) || (up && !left))
103         {    
104             int t=left|up;
105             if (j<n)
106             {
107                 code[j-1]=0,code[j]=t;
108                 dp[cur].push(encode(),dp[1-cur].f[k]+maze[i][j][r]);
109             }
110             if (i<m)
111             {
112                 code[j-1]=t,code[j]=0;
113                 dp[cur].push(encode(),dp[1-cur].f[k]+maze[i][j][d]);
114             }
115         }    
116         
117         if (!left && !up)
118         {
119             if (i<m && j<n) 
120             {
121                 code[j-1]=code[j]=MAXN-1;
122                 dp[cur].push(encode(),dp[1-cur].f[k]+maze[i][j][d]+maze[i][j][r]);
123             }
124         }
125     }
126 }
127 
128 void init()
129 {
130     scanf("%d%d",&m,&n);
131     char str[MAXN];
132     getchar();
133     gets(str);
134     memset(maze,0xef,sizeof(maze));
135     for (int i=1;i<=m;i++)
136     {
137         gets(str);
138         for (int j=1;j<=(n-1);j++)
139             maze[i][j][r]=maze[i][j+1][l]=str[2*j]-'0';
140         if (i!=m)
141         {
142             gets(str);
143             for (int j=1;j<=n;j++)
144                 maze[i][j][d]=maze[i+1][j][u]=str[2*j-1]-'0';
145         }
146         
147     }
148     gets(str);
149 }
150 void solve()
151 {
152     int cur=0;
153     dp[cur].clear();
154     dp[cur].push(0,0);
155     for (int i=1;i<=m;i++)
156         for (int j=1;j<=n;j++)//m和n写反掉啦 
157         {
158             cur^=1;
159             dp[cur].clear();
160             dpblank(i,j,cur);
161         }
162     ll ans=1e16;
163     for (int i=0;i<dp[cur].state.size();i++) ans=min(ans,dp[cur].f[i]);
164     printf("%lld
",ans);
165 }
166 
167 int main()
168 {
169     int T;
170     scanf("%d",&T);
171     while (T--)
172     {
173         init();
174         solve();
175     }
176     return 0;
177 }

[附赠:随机生成数据的程序，欢迎对拍~]

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     freopen("test.out","w",stdout);
 7     cout<<20<<endl;
 8     for (int t=1;t<=20;t++)
 9     {
10         int m=rand()%10+1,n=rand()%10+1;
11         cout<<m<<' '<<n<<endl;
12         for (int i=1;i<=(2*n+1);i++) cout<<'#';cout<<endl;
13         for (int i=1;i<=m;i++)
14         {
15             cout<<"# ";
16             for (int j=1;j<n;j++)
17             {
18                 int x=rand()%10;
19                 cout<<x<<' ';
20             }
21             cout<<"#"<<endl;
22             if (i==m) break;
23             cout<<'#';
24             for (int j=1;j<=n;j++)
25             {
26                 int x=rand()%10;
27                 cout<<x<<'#';
28             }
29             cout<<endl;
30         }
31         for (int i=1;i<=(2*n+1);i++) cout<<'#';cout<<endl;
32     }
33     return 0;
34 }