A Spy in the Metro UVA - 1025 dp

Lana ·

更新时间:2024-11-15

· 850 次阅读

题目链接：https://vjudge.net/problem/UVA-1025
紫书P268 书上是按照T从大到小
题意：第一行输入n，为n个车站，第2行为T，第三行表示从i到i+1车站所需时间，下面两行表示从1号车站向右走到n号车站有多少班车以及出发时间，最后两行表示从n号到1号的车出发时间，求在时间T到达n号车站在车站等待的最少时间。
思路：dp【i】【j】表示在第i分钟j号车站已经等待的时间。has_train【i】【j】【k】表示第i分钟车站j是否有车。k=0表示从左向右，k=1从右向左。当前状态有三种抉择：1.等待一分钟 2.坐车向左 3.坐车向右
错误的dp方程

                if(j=0)
                {
                    if(has_train[i-t[j]][j][0])
                        dp[i][j+1]=min(dp[i][j+1],dp[i-t[j]][j]);
                }
                if(j>1&&i-t[j-1]>=0)
                {
                    if(has_train[i-t[j-1]][j][1])
                        dp[i][j-1]=min(dp[i][j-1],dp[i-t[j-1]][j]);
                }
                dp[i+1][j]=min(dp[i][j]+1,dp[i+1][j]);//此处dp【i】【j】不一定是最优解
                //因为dp【i】【j】的最优解需要讨论dp【i】【j-1】和dp【i】【j+1】
                //但是dp【i】【j+1】尚未讨论，因此是错误的

#include 
using namespace std;
typedef long long LL;
const int maxn=50+5;
const int maxt=205;
const int inf=0x3f3f3f3f;
int t[maxn],has_train[maxt][maxn][2];
int dp[maxt][maxn];
int main()
{
    int kase=0,n,T;
    while(cin>>n&&n)
    {
        int m1,m2,d;
        scanf("%d",&T);
        for(int i=1; i>m1;
        while(m1--)
        {
            cin>>d;
            for(int j=1; j<=n-1; j++)
            {
                if(d>m2;
        while(m2--)
        {
            cin>>d;
            for(int j=n-1; j>=1; j--)
            {
                if(d<=T)
                {
                    has_train[d][j+1][1]=1;
                }
                d+=t[j];
            }
        }
        memset(dp,inf,sizeof(dp));
        dp[0][1]=0;
        for(int i=0; i<=T; i++)
        {
            for(int j=1; j=inf)
        {
            printf("impossible\n");
        }
        else
            cout<<dp[T][n]<<endl;
    }
    return 0;
}

作者：EHWWFFT.

dp IN spy metro

1024 个赞