【UVa】【DP】1632 Alibaba

UVa 1632 Alibaba

题目

◇题目传送门◆（由于UVa较慢，这里提供一个vjudge的链接）
◇题目传送门（vjudge）◆

题目大意

在x$x$轴上有N$N$个点，其中第i$i$个点的位置为xi$x_i$，且它在第di$d_i$秒后会消失。Alibaba可以从任意一点出发，且移动一个单位长度需要花一秒。求Alibaba访问完所有点的最短时间，无解时输出No solution。

思路

我们可以贪心地想，若我们在访问完区间[i,j]$[i,j]$中的点后，必然会位于点i$i$或点j$j$。所以，我们就将这道题转化为了区间DP。

定义状态f[i][j][0/1]$f[i][j][0/1]$为访问完区间[i,j]$[i,j]$中的点后，0$0$表示位于i$i$点，1$1$表示位于j$j$点。

则得出状态转移方程：

f[i][j][k]={min(f[i+1][j][0]+a[i+1]−a[i],f[i+1][j][1]+a[j]−a[i])min(f[i][j−1][0]+a[j]−a[i],f[i][j−1][1]+a[j]−a[j−1])k=0k=1$$f[i][j][k]=\{\begin{array}{ll}min(f[i+1][j][0]+a[i+1]-a[i],f[i+1][j][1]+a[j]-a[i])& k=0\\ min(f[i][j-1][0]+a[j]-a[i],f[i][j-1][1]+a[j]-a[j-1])& k=1\end{array}$$

其中1≤i≤N,i+1≤j≤N$1\le i\le N,i+1\le j\le N$。

解释一下：

首先对于状态f[i][j][0]$f[i][j][0]$，此时Alibaba需要走到点i$i$，画个图解释一下：

则对于状态f[i][j][0]$f[i][j][0]$，在f[i+1][j][0]+a[i+1]−a[i],f[i+1][j][1]+a[j]−a[i]$f[i+1][j][0]+a[i+1]-a[i],f[i+1][j][1]+a[j]-a[i]$之间取最小值即可。

对于状态f[i][j][1]$f[i][j][1]$，我们还是画个图解释：

即在f[i][j−1][0]+a[j]−a[i],f[i][j−1][1]+a[j]−a[j−1]$f[i][j-1][0]+a[j]-a[i],f[i][j-1][1]+a[j]-a[j-1]$之间取最小值。

接下来就是最后一步：

如何判断无解？

若在计算某一状态时发现当前所处的点的时间已经超出了这个点的d$d$，则将该状态赋值为INF。

最后判断min(f[1][N][0],f[1][N][1])$min(f[1][N][0],f[1][N][1])$是否大于等于INF即可。

正解代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int Maxn=10000;
const int INF=0x3f3f3f3f;

int N,p[Maxn+5],d[Maxn+5];
int f[Maxn+5][Maxn+5][2];

int main() {
    #ifdef LOACL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    while(scanf("%d",&N)!=EOF) {
        for(int i=1;i<=N;i++)
            scanf("%d %d",&p[i],&d[i]);
        for(int i=1;i<=N;i++)
            f[i][i][0]=f[i][i][1]=0;//访问区间[i,i]时所需时间为0
        for(int i=N-1;i>=1;i--)
            for(int j=i+1;j<=N;j++) {
                f[i][j][0]=min(f[i+1][j][0]+p[i+1]-p[i],f[i+1][j][1]+p[j]-p[i]);
                if(f[i][j][0]>=d[i])f[i][j][0]=INF;
                f[i][j][1]=min(f[i][j-1][0]+p[j]-p[i],f[i][j-1][1]+p[j]-p[j-1]);
                if(f[i][j][1]>=d[j])f[i][j][1]=INF;
            }
        int ans=min(f[1][N][0],f[1][N][1]);
        if(ans>=INF)puts("No solution");
        else printf("%d\n",ans);
        memset(f,0,sizeof f);
    }
    return 0;
}