首页 > ACM题库 > HDU-杭电 > HDU 4053-The Last Puzzle-动态规划-[解题报告]HOJ
2015
04-16

HDU 4053-The Last Puzzle-动态规划-[解题报告]HOJ

The Last Puzzle

问题描述 :

There is one last gate between the hero and the dragon. But opening the gate isn’t an easy task.

There were n buttons list in a straight line in front of the gate and each with an integer on it. Like other puzzles the hero had solved before, if all buttons had been pressed
down in any moment, the gate would open. So, in order to solve the puzzle, the hero must press all the button one by one.

After some trials, the hero found that those buttons he had pressed down would pop up after a while before he could press all the buttons down. He soon realized that
the integer on the button is the time when the button would automatic pop up after pressing it, in units of second. And he measured the distance between every button
and the first button, in units of maximum distance the hero could reach per second. Even with this information, the hero could not figure out in what order he should
press the buttons. So you talent programmers, are assigned to help him solve the puzzle.

To make the puzzle easier, assuming that the hero always took integral seconds to go from one button to another button and he took no time turnning around or pressing
a button down. And the hero could begin from any button.

输入:

The input file would contain multiple cases. Each case contains three lines. Process to the end of file.

The first line contains a single integer n(1 ≤ n ≤200), the number of buttons.

The second line contains n integers T1, T2, …, Tn, where Ti(1 ≤ Ti ≤ 1,000,000) is the time the ith button would automatic pop up after pressing it, in units of second.

The third line contains n integers D1, D2, …, Dn, where Di(1 ≤ Di ≤ 1,000,000) is the time hero needed to go between the ith button and the first button, in units of second.
The sequence will be in ascending order and the first element is always 0.

输出:

The input file would contain multiple cases. Each case contains three lines. Process to the end of file.

The first line contains a single integer n(1 ≤ n ≤200), the number of buttons.

The second line contains n integers T1, T2, …, Tn, where Ti(1 ≤ Ti ≤ 1,000,000) is the time the ith button would automatic pop up after pressing it, in units of second.

The third line contains n integers D1, D2, …, Dn, where Di(1 ≤ Di ≤ 1,000,000) is the time hero needed to go between the ith button and the first button, in units of second.
The sequence will be in ascending order and the first element is always 0.

样例输入:

2
4 3
0 3
2
3 3
0 3
4
5 200 1 2
0 1 2 3

样例输出:

1 2
Mission Impossible
1 2 4 3

Hint
In the second sample, no matter which button the hero pressed first, the button would always pop up before he press the other button. So there is no way to make all the button pressed down.

HDU 4053 ,提交返回WA,可能是spj有问题吧,害我提交n次以后伤心不已。。。

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;
const int maxn=220;
int n;
int t[maxn],d[maxn],ans[maxn];
int dp[maxn][maxn][2];
int w[maxn][maxn][2];
int dist[maxn][maxn];

void find(int l,int r,int p)
{
    if (dp[l][r][p]!=-1) return;
    if (p==0)
    {
        find(l+1,r,0);
        if (dp[l+1][r][0]>0&&t[l]>=dp[l+1][r][0]+dist[l][l+1])
        {
            dp[l][r][p]=dp[l+1][r][0]+dist[l][l+1];
            w[l][r][p]=0;
        }
        else
        dp[l][r][p]=0;

        find(l+1,r,1);
        if (dp[l+1][r][1]>0&&t[l]>=dp[l+1][r][1]+dist[l][r]&&(dp[l][r][p]==0||dp[l][r][p]>dp[l+1][r][1]+dist[l][r]))
        {
            dp[l][r][p]=dp[l+1][r][1]+dist[l][r];
            w[l][r][p]=1;
        }
    }
    else
    {
        find(l,r-1,1);
        if (dp[l][r-1][1]>0&&t[r]>=dp[l][r-1][1]+dist[r-1][r])
        {
            dp[l][r][p]=dp[l][r-1][1]+dist[r-1][r];
            w[l][r][p]=1;
        }
        else
        dp[l][r][p]=0;

        find(l,r-1,0);
        if (dp[l][r-1][0]>0&&t[r]>=dp[l][r-1][0]+dist[l][r]&&(dp[l][r][p]==0||dp[l][r][p]>dp[l][r-1][0]+dist[l][r]))
        {
            dp[l][r][p]=dp[l][r-1][0]+dist[l][r];
            w[l][r][p]=0;
        }
    }
}
void work(int l,int r,int p,int k)
{
    if (p==0) ans[k]=l;
    else ans[k]=r;
    if (k==n) return;
    if (p==0)
    work(l+1,r,w[l][r][p],k+1);
    else
    work(l,r-1,w[l][r][p],k+1);
}
void print()
{
    for (int i=1;i<n;i++)
    printf("%d ",ans[i]);
    printf("%d\n",ans[n]);
}
int main()
{
    //freopen("in.txt","r",stdin);
    while (~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&t[i]);
        for (int i=1;i<=n;i++)
            scanf("%d",&d[i]);
        for (int i=1;i<=n;i++)
        for (int j=i;j<=n;j++)
        dist[i][j]=dist[j][i]=d[j]-d[i];
        memset(dp,-1,sizeof(dp));
        for (int i=1;i<=n;i++)
            dp[i][i][0]=dp[i][i][1]=1;
        find(1,n,0);//站在l点,最快多长时间结束;
        if (dp[1][n][0]>0)
        {
            work(1,n,0,1);
            print();
            continue;
        }
        find(1,n,1);//站在r点,最快多长时间结束;
        if (dp[1][n][1]>0)
        {
            work(1,n,1,1);
            print();
            continue;
        }
        printf("Mission Impossible\n");
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/syjh_1026/article/details/17009753


  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”