ZOJ 3541 The Last Puzzle

区间dp。杭电上这题果然过不了，不知道那些A了的是怎么A的。。对于区间[ l , r ]一定是从最左边或者从最右边开始按的，因为假如从中间任意位置 k 开始按的话，一定要按最左边的那个，也一定要按最右边的那个，这样的话一定会经过 k ，这样的话，对于 k 来说这样一定不是最优解。于是问题就转化为了区间dp了。可以用dp[ l ][ r ][0] 表示从左边开始按，把区间走完需要多长时间（要满足时间条件t [ i ]）。dp[ l ][ r ][1] 表示从右边开始按，把区间走完需要多长时间（要满足时间条件t [ i ]）。这样的话有状态转移方程：

dp[ l ][ r ][0] = min(dp[l + 1][r][0] + d[l + 1] - d[l],dp[l + 1][r][1] + d[r] - d[l]);

dp[ l ][ r ][1] = min(left = dp[l][r - 1][0] + d[r] - d[l,dp[l][r - 1][1] + d[r] - d[r - 1]);

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define CLR(a, b) memset(a, b, sizeof(a))

using namespace std;

const int N = 222;
const LL INF = 1e18;
LL dp[N][N][2];
int path[N][N][2];
int t[N], d[N];

int main()
{
    int n, i, l, r, f;
    LL left, right;
    while(scanf("%d", &n) != EOF)
    {
        for(i = 1; i <= n; i ++)
        {
            scanf("%d", &t[i]);
        }
        for(i = 1; i <= n; i ++)
        {
            scanf("%d", &d[i]);
        }
        CLR(dp, 0);
        for(i = 1; i < n; i ++)
        {
            for(l = 1; i + l <= n; l ++)
            {
                r = i + l;
                left = dp[l + 1][r][0] + d[l + 1] - d[l];
                right = dp[l + 1][r][1] + d[r] - d[l];
                if(left < right)
                {
                    dp[l][r][0] = left;
                    path[l][r][0] = 0;
                }
                else
                {
                    dp[l][r][0] = right;
                    path[l][r][0] = 1;
                }
                if(t[l] <= dp[l][r][0]) dp[l][r][0] = INF;
                left = dp[l][r - 1][0] + d[r] - d[l];
                right = dp[l][r - 1][1] + d[r] - d[r - 1];
                if(left < right)
                {
                    dp[l][r][1] = left;
                    path[l][r][1] = 0;
                }
                else
                {
                    dp[l][r][1] = right;
                    path[l][r][1] = 1;
                }
                if(t[r] <= dp[l][r][1]) dp[l][r][1] = INF;
            }
        }
        l = 1; r = n;
        if(dp[1][n][0] < INF)
        {
            f = path[1][n][0];
            printf("%d", l ++);
        }
        else if(dp[1][n][1] < INF)
        {
            f = path[1][n][1];
            printf("%d", r --);
        }
        else
        {
            puts("Mission Impossible");
            continue;
        }
        while(l <= r)
        {
            if(f == 0)
            {
                f = path[l][r][0];
                printf(" %d", l ++);
            }
            else
            {
                f = path[l][r][1];
                printf(" %d", r --);
            }
        }
        puts("");
    }
}