当前位置：首页 > news >正文

UVA1025 A Spy in the Metro （dp）

news 来源：原创 2024/5/20 22:37:30

传送门

首先推状态转移方程，影响到决策的只有当前的时间和所处的车站，可以用dp[i][j]表示时刻i间谍在车站j，最少还需等待多长时间。如果达到目标即满足dp[T][n]有解，那么考虑逆序递推，从终点开始考虑如何一步步状态转移到起点，那么就是只有时间为T，当前车站为n的状态才能符合要求，这里时间t是主要决策，故dp[T][n]设为0，其他的dp[T][i]为inf

因为每趟车的出发时间给定且两个车站之间的路程时间给定，那么我们可以预处理每一辆车hsa_train[i][j][0\1]表示时刻i，在车站j是否有向右/左开的车

然后每次都有三个状态去转移：

1.等待1分钟（1个时间单位）

dp[i][j]=dp[i+1][j]+1；即当前状态由前一个时间单位仍在j车站的状态得到

2.如果有则搭乘向右开的车

dp[i][j]=min(dp[i][j],dp[ i+t[j] ][j+1])；即当前状态是由前一个状态向左搭车得到的，因此后一个车站到左边的车站等同于左边的车站到后一个车站的时间t[j]

3.如果有则搭乘向左开的车

dp[i][j]=min(dp[i][j],dp[ i+t[j-1] ][j-1])；即当前状态是由前一个状态向右搭车得到的，因此必须加上当前车向左走间t[j-1]的时间才能到达上一个状态dp[?][j-1]

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

int n,T,m1,m2;
bool has_train[300][55][2];
int t[maxn],dp[300][55];

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int kase=0;
    while(cin>>n && n){
        cin>>T;
        memset(has_train,0,sizeof has_train);
        for(int i=1;i<n;i++) cin>>t[i];
        cin>>m1;
        for(int i=1,cur;i<=m1;i++){
            cin>>cur;
            for(int j=1;j<=n;j++){
                has_train[cur][j][0]=1;
                cur+=t[j];
            }
        }
        cin>>m2;
        for(int i=1,cur;i<=m2;i++){
            cin>>cur;
            for(int j=n;j>=1;j--){
                has_train[cur][j][1]=1;
                cur+=t[j-1];
            }
        }
        //cout<<"now is here"<<endl;
        memset(dp,0,sizeof dp);
        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+t[j]<=T)
                    dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]);
                if(j>1 && has_train[i][j][1] && i+t[j-1]<=T)
                    dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]);
            }
        cout<<"Case Number "<<++kase<<": ";
        if(dp[0][1]>=inf) cout<<"impossible\n";
        else cout<<dp[0][1]<<"\n";
    }
    return 0;
}