本文主要是介绍动态规划--uva1025 城市里的间谍，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
影响决策的因素有当前时间t和所处车站，所以dp[t][n]，2维。
求等待最短时间，即dp[t][n]
决策有3个，等待1分钟，向右坐火车，向左坐火车。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespacestd;
const int maxn =255;
const int INF =1 << 25;
int dis[55];
int d[maxn],e[maxn];
bool has_train[maxn][55][2];
int dp[maxn][55];
int n,t,m1,m2;
void f()
{
for (int i =1; i <= n -1; i ++) {
dp[t][i] =INF;
}
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(j <n && has_train[i][j][0] && i +dis[j] <= t)
{
dp[i][j] =min(dp[i][j],dp[i +dis[j]][j + 1]);
}
if(j >1 && has_train[i][j][1] && i +dis[j - 1] <=t)
{
dp[i][j] =min(dp[i][j],dp[i +dis[j - 1]][j -1]);
}
}
}
}
int main()
{
int kce =0;
while (cin >>n && n) {
memset(dis,0, sizeof(dis));
memset(has_train,0, sizeof(has_train));
memset(d,0, sizeof(d));
memset(e,0, sizeof(e));
memset(dp,0, sizeof(dp));
cin >>t;
for (int i =1; i <= n -1; i ++) {
scanf("%d",&dis[i]);
}
cin >>m1;
for (int i =1; i <= m1; i ++) {
scanf("%d",&d[i]);
}
cin >>m2;
for (int i =1; i <= m2; i ++) {
scanf("%d",&e[i]);
}
for (int i =1; i <= m1; i ++) {
int tmp =d[i];
for (int j =1; j < n; j ++) {
has_train[tmp][j][0] =true;
// cout << "when time " << tmp<< " at station " << j <<" has train to right" << endl;
tmp += dis[j];
}
}
for (int i =1; i <= m2; i ++) {
int tmp =e[i];
for (int j =n; j > 1; j --) {
has_train[tmp][j][1] =true;
// cout << "when time " << tmp<< " at station " << j <<" has train to left" << endl;
tmp += dis[j -1];
}
}
f();
cout <<"Case Number " << ++kce <<": " ;
if (dp[0][1] >= INF) {
cout <<"impossible\n";
}
elsecout << dp[0][1] <<endl;
}
return0;
}
这篇关于动态规划--uva1025 城市里的间谍的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
