http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=847&page=show_problem&problem=3466

状态:dp(i,j)——在时刻i,你在车站j的最少等待时间。
转移:

  1. 等1分钟
  2. 搭乘向右开的车
  3. 搭乘向左开的车(在车上逗留嘛~)

注意用一个bool数组标记当前时刻有没有从当前车站出发的列车。

const int mx = 55;

int t[mx], arrive[mx], dp[205][mx];
bool has[205][mx][2];

int solve(int n, int T)
{
    mem(dp[T], 0x3f);
    dp[T][n] = 0;
    int i, j;
    rFor(i, T - 1) Forr(j, 1, n + 1)
    {
        dp[i][j] = dp[i + 1][j] + 1;
        if (j < n && has[i][j][0] && i + t[j] <= T) Qmin(dp[i][j], dp[i + t[j]][j + 1]);
        if (j > 1 && has[i][j][1] && i + t[j - 1] <= T) Qmin(dp[i][j], dp[i + t[j - 1]][j - 1]);
    }
    return dp[0][1] >= inf ? -1 : dp[0][1];
}

int main()
{
    int cas = 0, n, T, i, m, d, ans;
    while (SII(n, T), n)
    {
        Pcas();
        Forr(i, 1, n) SI(t[i]), arrive[i + 1] = arrive[i] + t[i];
        mem(has, 0);
        SI(m);
        while (m--)
        {
            SI(d);
            has[d][1][0] = true;
            Forr(i, 2, n + 1)
            {
                if (d + arrive[i] > T) break;
                has[d + arrive[i]][i][0] = true;
            }
        }
        SI(m);
        while (m--)
        {
            SI(d);
            has[d][n][1] = true;
            rForr(i, n - 1, 1)
            {
                if (d + arrive[n] - arrive[i] > T) break;
                has[d + arrive[n] - arrive[i]][i][1] = true;
            }
        }
        ans = solve(n, T);
        ~ans ? PI(ans) : puts("impossible");
    }
    return 0;
}

Comments

comments powered by Disqus