【动态规划】[UVA1025]A Spy in the Metro 城市里的间谍

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 using namespace std;
  5 const int N=55;
  6 const int M=210;
  7 const int INF=1e8;
  8 int n,t,l,r,kcase;//n车站数，t时间，l向右车辆数，kcase样例数
  9 int station_time[N];//车站之间的时间
 10 int have_train[M][N][3],dp[M][N];
 11 void test()
 12 {
 13     cout<<'n'<<n<<'t'<<t<<endl;
 14     for (int i=0;i<n;i++)
 15     {
 16         cout<<station_time[i]<<' ';
 17     }
 18     cout<<endl;
 19     for (int i=0;i<=t;i++)
 20     {
 21         for (int j=0;j<=n;j++)
 22         {
 23             printf("[%9d]",dp[i][j]);
 24         }
 25         printf("
");
 26     }
 27     getchar();
 28 }
 29 void init()
 30 {
 31     cin>>t;
 32     memset(station_time,0,sizeof(station_time));
 33     for (int i=0;i<n-1;i++)
 34     {
 35         cin>>station_time[i];
 36     }
 37     cin>>r;
 38     memset(have_train,0,sizeof(have_train));
 39     while (r--)
 40     {
 41         int d;
 42         cin>>d;
 43         for (int j=1;j<n;j++)
 44         {
 45             if (d<=t)
 46             {
 47                 have_train[d][j][0]=1;
 48             }
 49             d+=station_time[j-1];
 50         }
 51     }
 52     cin>>l;
 53     while (l--)
 54     {
 55         int d;
 56         cin>>d;
 57         for (int j=n;j>1;j--)
 58         {
 59             if (d<=t)
 60             {
 61                 have_train[d][j][1]=1;
 62             }
 63             d+=station_time[j-2];
 64         }
 65     }
 66 }
 67 void dpp()
 68 {
 69     memset(dp,0,sizeof(dp));
 70     for (int j=1;j<=n;j++)
 71     {
 72         dp[t][j]=INF;
 73     }
 74     dp[t][n]=0;
 75     for (int i=t-1;i>=0;i--)//注意i>=0!
 76     {
 77         for (int j=1;j<=n;j++)
 78         {
 79             dp[i][j]=dp[i+1][j]+1;
 80             if (j<n&&have_train[i][j][0]&&i+station_time[j-1]<=t)
 81             {
 82                 dp[i][j]=min(dp[i][j],dp[i+station_time[j-1]][j+1]);
 83             }
 84             if (j>1&&have_train[i][j][1]&&i+station_time[j-2]<=t)//注意判断条件不要写错！
 85             {
 86                 dp[i][j]=min(dp[i][j],dp[i+station_time[j-2]][j-1]);
 87             }
 88         }
 89 
 90     }
 91 //    test();
 92     cout<<"Case Number "<<kcase++<<": ";
 93     if (dp[0][1]>=INF)
 94     {
 95         cout<<"impossible"<<endl;
 96     }
 97     else
 98     {
 99         cout<<dp[0][1]<<endl;
100     }
101 }
102 int main()
103 {
104     kcase=1;
105 //    freopen("btext.txt","r",stdin);
106     while (cin>>n&&n)
107     {
108         init();
109         dpp();
110     }
111 
112     return 0;
113 }