【luogu2583】地铁间谍

https://www.luogu.org/problem/show?pid=2583

设在时刻i，车站j到结束最短需要等待f(i,j)分钟，得状态转移方程：

f(i,j)=min{
     f(i+1,j)+1
     f(i+t[j-1],j-1) (若时刻i有向左走的车)
     f(i+t[j],j+1) (若时刻i有向右走的车)
}
因此需要预处理每一时刻有没有车可以坐。

初始值f(t,n)=0，其他均为∞。

 #include <iostream>

 #include <cstring>

 #define maxt 210

 #define maxn 60

 #define inf 1000

 using namespace std;

 bool has_train[maxt][maxn][];

 int dp[maxt][maxn];

 int n, tt, t[maxn], m1, m2, d;

 int main()

 {

     int cnt = ;

     while (true)

     {

         cin >> n;

         if (n == ) break;

         cin >> tt;

         for (int i = ; i<n; i++) cin >> t[i];

         //预处理has_train数组

         memset(has_train, false, maxt * maxn * );

         cin >> m1;

         while (m1--)

         {

             cin >> d;

             for (int j = ; j <= n -  && d <= tt; j++)

             {

                 has_train[d][j][] = true;

                 d += t[j];

             }

         }

         cin >> m2;

         while (m2--)

         {

             cin >> d;

             for (int j = n; j >=  && d <= tt; j--)

             {

                 has_train[d][j][] = true;

                 d += t[j - ];

             }

         }

         //初始化dp数组

         for (int i = ; i <= n; i++)

             dp[tt][i] = inf;

         dp[tt][n] = ;

         for (int i = tt - ; i >= ; i--)

         {

             for (int j = ; j <= n; j++)

             {

                 dp[i][j] = dp[i + ][j] + ; //+1s

                 if (i + t[j] <= tt && j +  <= n && has_train[i][j][])

                     dp[i][j] = min(dp[i][j], dp[i + t[j]][j + ]); //向右走

                 if (i + t[j - ] <= tt && j -  >=  && has_train[i][j][])

                     dp[i][j] = min(dp[i][j], dp[i + t[j - ]][j - ]); //向左走

             }

         }

         if (dp[][]<inf)

             cout << "Case Number " << cnt << ": " << dp[][] << endl;

         else

             cout << "Case Number " << cnt << ": impossible" << endl;

         cnt++;

     }

     return ;

 }