都市のスパイ(A Spy in the Metro UVa 1025)の最も詳しい問題解
15675 ワード
アキュムレータ転送ゲート:
http://blog.csdn.net/NOIAu/article/details/71775000
タイトル転送ゲート:
https://vjudge.net/problem/UVA-1025
タイトル内容:
Secret agent Maria was sent to Algorithms City to carry out an especially dangerous mission. After several thrilling events we nd her in the rst station of Algorithms City Metro, examining the time table. The Algorithms City Metro consists of a single line with trains running both ways, so its time table is not complicated. Maria has an appointment with a local spy at the last station of Algorithms City Metro. Maria knows that a powerful organization is after her. She also knows that while waiting at a station, she is at great risk of being caught. To hide in a running train is much safer, so she decides to stay in running trains as much as possible, even if this means traveling backward and forward. Maria needs to know a schedule with minimal waiting time at the stations that gets her to the last station in time for her appointment. You must write a program that nds the total waiting time in a best schedule for Maria. The Algorithms City Metro system has N stations, consecutively numbered from 1 to N. Trains move in both directions: from the rst station to the last station and from the last station back to the rst station. The time required for a train to travel between two consecutive stations is xed since all trains move at the same speed. Trains make a very short stop at each station, which you can ignore for simplicity. Since she is a very fast agent, Maria can always change trains at a station even if the trains involved stop in that station at the same time.
入力:
The input le contains several test cases. Each test case consists of seven lines with information as follows. Line 1. The integer N (2 N 50), which is the number of stations. Line 2. The integer T (0 T 200), which is the time of the appointment. Line 3. N 1 integers: t1; t2; : : : ; tN1 (1 ti 20), representing the travel times for the trains between two consecutive stations: t1 represents the travel time between the rst two stations, t2 the time between the second and the third station, and so on. Line 4. The integer M1 (1 M1 50), representing the number of trains departing from the rst station. Line 5. M1 integers: d1; d2; : : : ; dM1 (0 di 250 and di < di+1), representing the times at which trains depart from the rst station. Line 6. The integer M2 (1 M2 50), representing the number of trains departing from the N-th station. Line 7. M2 integers: e1; e2; : : : ; eM2 (0 ei 250 and ei < ei+1) representing the times at which trains depart from the N-th station. The last case is followed by a line containing a single zero.
出力:
For each test case, print a line containing the case number (starting with 1) and an integer representing the total waiting time in the stations for a best schedule, or the word `impossible’ in case Maria is unable to make the appointment. Use the format of the sample output.
問題の核心は逆押しの思想である
この問題は最低どのくらい待つ必要があるかを聞くと、自然にdpを使うことを考えますが、どうやってこの問題を処理しますか?時刻iをdp[i][j]で表すことができます.あなたは今j番目の駅にいます.少なくともどのくらい待つ必要がありますか.私たちが知っているのは、T時点で、あなたは必ずn番目の駅でスパイの任務を完成しなければならないので、dp[T][n]=0です.この位置から反転することができて、例えば私は時刻T-1で依然として駅nに位置することができて、あるいは左へ行く車があれば私は左へ車に乗る可能性があります;では、dp[i][j]の状態遷移には、3つの遷移方式があります.
意思決定1:
私はその場でじっとしていて、この時待つ時間はdp[i+1][j]から移ってきて、dp[i+1][j]の基礎の上で+1が必要です;私はj+1の時の最適待ち値に基づいて、1つの時間を待つ(時間が後から逆に押されるので、dp配列は少なくともどれだけの時間を待つ必要があるかを示すことに注意)
意思決定2:
右に移動し、右に車があればdp[i][j]がdp[i+t[j]][j+1]からdp[i+t[j]][j+1]に移行する必要があるのは時刻i+t[j]の時(右から次の駅j+1駅までの時の最適値に相当)であり、逆押しであるため、dp[i+t[j]][j+1]の値はdp[i][j]より先に算出されるので、dp移行は合理的である
意思決定3:
左に移動し、左に車があればdp[i][j]がdp[i+t[j-1][j-1]から移行する必要があり、原理は上と同じで、左にt[j-1]の時間がかかり、i+t[j-1]の時刻、位置が左一局のj-1局にあるときの最適値は、ループの中で先にループするのがiであり、しかも逆ループであるため、dp[i+t[j-1][j-1][j-1]の値も先に算出され、だからdp移転は合理的です
では、ある時点で左または右にdp移行したかどうかをどのように判定するか、has_a _train[i][j][2]配列はhas_を格納するa _train[i][j][0]はi時刻がj駅にあり、左に走る地下鉄があるかどうかを示している.has_a _train[i][j][1]は、i時刻がj駅にあり、右に走る地下鉄の前処理と出力があるかどうかを示すコードは以下の通りである.
前処理を行うとO(1)のdp転送が可能になり,非常に便利になり,具体的なdp転送はこのようになる.
だからここまで完全に理解したはずだこの問題には今完全なコードが貼られている.
気をつけてねhas_a _train配列の初期化
http://blog.csdn.net/NOIAu/article/details/71775000
タイトル転送ゲート:
https://vjudge.net/problem/UVA-1025
タイトル内容:
Secret agent Maria was sent to Algorithms City to carry out an especially dangerous mission. After several thrilling events we nd her in the rst station of Algorithms City Metro, examining the time table. The Algorithms City Metro consists of a single line with trains running both ways, so its time table is not complicated. Maria has an appointment with a local spy at the last station of Algorithms City Metro. Maria knows that a powerful organization is after her. She also knows that while waiting at a station, she is at great risk of being caught. To hide in a running train is much safer, so she decides to stay in running trains as much as possible, even if this means traveling backward and forward. Maria needs to know a schedule with minimal waiting time at the stations that gets her to the last station in time for her appointment. You must write a program that nds the total waiting time in a best schedule for Maria. The Algorithms City Metro system has N stations, consecutively numbered from 1 to N. Trains move in both directions: from the rst station to the last station and from the last station back to the rst station. The time required for a train to travel between two consecutive stations is xed since all trains move at the same speed. Trains make a very short stop at each station, which you can ignore for simplicity. Since she is a very fast agent, Maria can always change trains at a station even if the trains involved stop in that station at the same time.
入力:
The input le contains several test cases. Each test case consists of seven lines with information as follows. Line 1. The integer N (2 N 50), which is the number of stations. Line 2. The integer T (0 T 200), which is the time of the appointment. Line 3. N 1 integers: t1; t2; : : : ; tN1 (1 ti 20), representing the travel times for the trains between two consecutive stations: t1 represents the travel time between the rst two stations, t2 the time between the second and the third station, and so on. Line 4. The integer M1 (1 M1 50), representing the number of trains departing from the rst station. Line 5. M1 integers: d1; d2; : : : ; dM1 (0 di 250 and di < di+1), representing the times at which trains depart from the rst station. Line 6. The integer M2 (1 M2 50), representing the number of trains departing from the N-th station. Line 7. M2 integers: e1; e2; : : : ; eM2 (0 ei 250 and ei < ei+1) representing the times at which trains depart from the N-th station. The last case is followed by a line containing a single zero.
出力:
For each test case, print a line containing the case number (starting with 1) and an integer representing the total waiting time in the stations for a best schedule, or the word `impossible’ in case Maria is unable to make the appointment. Use the format of the sample output.
問題の核心は逆押しの思想である
この問題は最低どのくらい待つ必要があるかを聞くと、自然にdpを使うことを考えますが、どうやってこの問題を処理しますか?時刻iをdp[i][j]で表すことができます.あなたは今j番目の駅にいます.少なくともどのくらい待つ必要がありますか.私たちが知っているのは、T時点で、あなたは必ずn番目の駅でスパイの任務を完成しなければならないので、dp[T][n]=0です.この位置から反転することができて、例えば私は時刻T-1で依然として駅nに位置することができて、あるいは左へ行く車があれば私は左へ車に乗る可能性があります;では、dp[i][j]の状態遷移には、3つの遷移方式があります.
意思決定1:
私はその場でじっとしていて、この時待つ時間はdp[i+1][j]から移ってきて、dp[i+1][j]の基礎の上で+1が必要です;私はj+1の時の最適待ち値に基づいて、1つの時間を待つ(時間が後から逆に押されるので、dp配列は少なくともどれだけの時間を待つ必要があるかを示すことに注意)
dp[i][j]=dp[i+1][j]+1;意思決定2:
右に移動し、右に車があればdp[i][j]がdp[i+t[j]][j+1]からdp[i+t[j]][j+1]に移行する必要があるのは時刻i+t[j]の時(右から次の駅j+1駅までの時の最適値に相当)であり、逆押しであるため、dp[i+t[j]][j+1]の値はdp[i][j]より先に算出されるので、dp移行は合理的である
dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]);意思決定3:
左に移動し、左に車があればdp[i][j]がdp[i+t[j-1][j-1]から移行する必要があり、原理は上と同じで、左にt[j-1]の時間がかかり、i+t[j-1]の時刻、位置が左一局のj-1局にあるときの最適値は、ループの中で先にループするのがiであり、しかも逆ループであるため、dp[i+t[j-1][j-1][j-1]の値も先に算出され、だからdp移転は合理的です
dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]);では、ある時点で左または右にdp移行したかどうかをどのように判定するか、has_a _train[i][j][2]配列はhas_を格納するa _train[i][j][0]はi時刻がj駅にあり、左に走る地下鉄があるかどうかを示している.has_a _train[i][j][1]は、i時刻がj駅にあり、右に走る地下鉄の前処理と出力があるかどうかを示すコードは以下の通りである.
bool init(){
memset(has_a_train,false,sizeof(has_a_train));
scanf("%d",&n);
if(n==0) return false;
scanf("%d",&T);
for(int i=1;i<=n-1;i++) scanf("%d",&t[i]);
scanf("%d",&M1);
for(int i=1;i<=M1;i++){
scanf("%d",&dl[i]);
int timer=dl[i];
if(timer<=T) has_a_train[timer][1][1]=true;
for(int i=1;i<=n-1;i++){
if(timer+t[i]<=T){
has_a_train[timer+t[i]][i+1][1]=true;
timer+=t[i];
}
else break;
}
}
scanf("%d",&M2);
for(int i=1;i<=M2;i++){
scanf("%d",&dr[i]);
int timer=dr[i];
if(dr[i]<=T) has_a_train[timer][n][0]=true;
for(int i=n-1;i>=1;i--){
if(timer+t[i]<=T){
has_a_train[timer+t[i]][i][0]=true;
timer+=t[i];
}
else break;
}
}
return true;
}前処理を行うとO(1)のdp転送が可能になり,非常に便利になり,具体的なdp転送はこのようになる.
void dpp(){
for(int i=1;i<=n-1;i++) dp[T][i]=MAXNN;
dp[T][n]=0;
for(int i=T-1;i>=0;i--){
for(int j=1;j<=n;j++){
dp[i][j]=dp[i+1][j]+1;
if(j1]&&i+t[j]<=T)
dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]);
if(j>1&&has_a_train[i][j][0]&&i+t[j-1]<=T)
dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]);
}
}
} だからここまで完全に理解したはずだこの問題には今完全なコードが貼られている.
#include1]&&i+t[j]<=T)
dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]);
if(j>1&&has_a_train[i][j][0]&&i+t[j-1]<=T)
dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]);
}
}
}
void print(){
cnt++;
printf("Case Number %d: ",cnt);
if(dp[0][1]>=MAXNN) printf("impossible
");
else printf("%d
",dp[0][1]);
}
int main(){
while(init()){
dpp();
print();
}
return 0;
} 
気をつけてねhas_a _train配列の初期化