HDu 1964のプラグDP最適値を求める
6385 ワード
Pipes
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 477 Accepted Submission(s): 238
Problem Description
The construction of office buildings has become a very standardized task. Pre-fabricated modules are combined according to the customer’s needs, shipped from a faraway factory, and assembled on the construction site. However, there are still some tasks that require careful planning, one example being the routing of pipes for the heating system.
Amodern office building ismade up of squaremodules, one on each floor being a service module from which (among other things) hot water is pumped out to the other modules through the heating pipes. Each module (including the service module) will have heating pipes connecting it to exactly two of its two to four neighboring modules. Thus, the pipes have to run in a circuit, from the service module, visiting each module exactly once, before finally returning to the service module. Due to different properties of the modules, having pipes connecting a pair of adjacent modules comes at different costs. For example, some modules are separated by thick walls, increasing the cost of laying pipes. Your task is to, given a description of a floor of an office building, decide the cheapest way to route the heating pipes.
Input
The first line of input contains a single integer, stating the number of floors to handle. Then follow n floor descriptions, each beginning on a new line with two integers, 2 <= r <= 10 and 2 <= c <= 10, defining the size of the floor – r-by-c modules. Beginning on the next line follows a floor description in ASCII format, in total 2r + 1 rows, each with 2c + 2 characters, including the final newline. All floors are perfectly rectangular, and will always have an even number of modules. All interior walls are represented by numeric characters, ’0’ to ’9’, indicating the cost of routing pipes through the wall (see sample input).
Output
For each test case, output a single line with the cost of the cheapest route.
Sample Input
Sample Output
意味が分かりにくいので、直接入力を見て、スペースは通過可能な点を表し、数字は隣接する点の間を通過するのに必要な費用を表します.
すべての点を通過して原点に戻るのに必要な最小限の費用を聞く
プラグDPテンプレート問題は、ある状態に到達する数を最小限にするだけでよい
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 477 Accepted Submission(s): 238
Problem Description
The construction of office buildings has become a very standardized task. Pre-fabricated modules are combined according to the customer’s needs, shipped from a faraway factory, and assembled on the construction site. However, there are still some tasks that require careful planning, one example being the routing of pipes for the heating system.
Amodern office building ismade up of squaremodules, one on each floor being a service module from which (among other things) hot water is pumped out to the other modules through the heating pipes. Each module (including the service module) will have heating pipes connecting it to exactly two of its two to four neighboring modules. Thus, the pipes have to run in a circuit, from the service module, visiting each module exactly once, before finally returning to the service module. Due to different properties of the modules, having pipes connecting a pair of adjacent modules comes at different costs. For example, some modules are separated by thick walls, increasing the cost of laying pipes. Your task is to, given a description of a floor of an office building, decide the cheapest way to route the heating pipes.
Input
The first line of input contains a single integer, stating the number of floors to handle. Then follow n floor descriptions, each beginning on a new line with two integers, 2 <= r <= 10 and 2 <= c <= 10, defining the size of the floor – r-by-c modules. Beginning on the next line follows a floor description in ASCII format, in total 2r + 1 rows, each with 2c + 2 characters, including the final newline. All floors are perfectly rectangular, and will always have an even number of modules. All interior walls are represented by numeric characters, ’0’ to ’9’, indicating the cost of routing pipes through the wall (see sample input).
Output
For each test case, output a single line with the cost of the cheapest route.
Sample Input
3
4 3
#######
# 2 3 #
#1#9#1#
# 2 3 #
#1#7#1#
# 5 3 #
#1#9#1#
# 2 3 #
#######
4 4
#########
# 2 3 3 #
#1#9#1#4#
# 2 3 6 #
#1#7#1#5#
# 5 3 1 #
#1#9#1#7#
# 2 3 0 #
#########
2 2
#####
# 1 #
#2#3#
# 4 #
#####
Sample Output
28
45
10
意味が分かりにくいので、直接入力を見て、スペースは通過可能な点を表し、数字は隣接する点の間を通過するのに必要な費用を表します.
すべての点を通過して原点に戻るのに必要な最小限の費用を聞く
プラグDPテンプレート問題は、ある状態に到達する数を最小限にするだけでよい
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <iomanip>
#define INF 99999999
typedef long long LL;
using namespace std;
const int MAX=100000+10;
const int N=10+10;
int n,m,size,index;
int mp[N][N],w[N][N][N][N],total[2],bit[N];//w[i][j][k][t] i,j->k,t
int head[MAX],next[MAX],Hash[MAX];
LL dp[2][MAX],state[2][MAX],sum;//dp
void Init(){
memset(mp,0,sizeof mp);
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)mp[i][j]=1;
index=0;
sum=INF;
total[index]=1;
dp[index][1]=0;
state[index][1]=0;
}
void HashCalState(LL s,LL v){
int pos=s%MAX;
for(int i=head[pos];i != -1;i=next[i]){
if(state[index][Hash[i]] == s){
dp[index][Hash[i]]=min(dp[index][Hash[i]],v);
return;
}
}
++total[index];
state[index][total[index]]=s;
dp[index][total[index]]=v;
//
Hash[size]=total[index];
next[size]=head[pos];
head[pos]=size++;
}
void DP(){// 4
for(int i=1;i<=n;++i){
for(int k=1;k<=total[index];++k)state[index][k]<<=2;// (0) , (0)
for(int j=1;j<=m;++j){// i,j
memset(head,-1,sizeof head);
size=0;
index=index^1;
total[index]=0;
for(int k=1;k<=total[index^1];++k){//
LL s=state[index^1][k];
LL v=dp[index^1][k];
int p=(s>>bit[j-1])%4;
int q=(s>>bit[j])%4;
// mp[i][j] ,
if(!p && !q){//
if(!mp[i][j+1] || !mp[i+1][j])continue;
s=s+(1<<bit[j-1])+2*(1<<bit[j]);
v=v+w[i][j][i][j+1]+w[i][j][i+1][j];
HashCalState(s,v);
}else if(!p && q){
if(mp[i][j+1])HashCalState(s,v+w[i][j][i][j+1]);
if(mp[i+1][j]){
s=s+q*(1<<bit[j-1])-q*(1<<bit[j]);
v=v+w[i][j][i+1][j];
HashCalState(s,v);
}
}else if(p && !q){
if(mp[i+1][j])HashCalState(s,v+w[i][j][i+1][j]);
if(mp[i][j+1]){
s=s-p*(1<<bit[j-1])+p*(1<<bit[j]);
v=v+w[i][j][i][j+1];
HashCalState(s,v);
}
}else if(p == 1 && q == 1){
int b=1;
for(int t=j+1;t<=m;++t){
int a=(s>>bit[t])%4;
if(a == 1)++b;
if(a == 2)--b;
if(!b){
s=s+(1<<bit[t])-2*(1<<bit[t]);
break;
}
}
s=s-(1<<bit[j-1])-(1<<bit[j]);
HashCalState(s,v);
}else if(p == 2 && q == 2){
int b=1;
for(int t=j-2;t>=0;--t){
int a=(s>>bit[t])%4;
if(a == 2)++b;
if(a == 1)--b;
if(!b){
s=s-(1<<bit[t])+2*(1<<bit[t]);
break;
}
}
s=s-2*(1<<bit[j-1])-2*(1<<bit[j]);
HashCalState(s,v);
}else if(p == 1 && q == 2){
if(i == n && j == m)sum=min(sum,v);
}else if(p == 2 && q == 1){
s=s-2*(1<<bit[j-1])-(1<<bit[j]);
HashCalState(s,v);
}
}
}
}
}
int main(){
for(int i=0;i<N;++i)bit[i]=i<<1;
int t;
char s[N+N];
scanf("%d",&t);
while(t--){
scanf("%d%d%*c",&n,&m);
Init();
gets(s);
for(int i=1;i<=n;++i){
gets(s);
for(int j=2;j<2*m+1;j+=2){
w[i][j/2][i][j/2+1]=s[j]-'0';
}
gets(s);
for(int j=1;j<2*m+1;j+=2){
w[i][j/2+1][i+1][j/2+1]=s[j]-'0';
}
}
DP();
printf("%lld
",sum);
}
return 0;
}