POJ 1661 动态规划 Help Jimmy

动态规划，意思简洁明了。

排序，n^2做法。

每次检测可行的长条，最高的永远是起始点。

dp[i][0]表示第i个长条的左边下去最短的时间。

dp[i][1]表示第i个长条的右边下去最短的时间。

#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;
int n;
int INF=2000000;
struct Edge
{
    int left,right,high;
} a[1010];
int dp[1010][2];
int cmp(Edge a,Edge b)
{
    return a.high>b.high;
}
int main()
{
    int T;
    scanf ("%d",&T);
    while (T--)
    {
        scanf ("%d",&n);
        int xx,yy,max_high,i,j;
        scanf ("%d%d%d",&xx,&yy,&max_high);
        a[0].left=xx;
        a[0].right=xx;
        a[0].high=yy;
        for (i=1; i<=n; i++)
            scanf ("%d%d%d",&a[i].left,&a[i].right,&a[i].high);
        sort(a+1,a+n+1,cmp);
        dp[n][0]=a[n].high;
        dp[n][1]=a[n].high;
        for (i=n-1; i>=0; i--)
        {
            for (j=i+1; j<=n; j++)
                if (a[j].left<=a[i].left&&a[j].right>=a[i].left)
                    break;
            if (j<=n)
            {
                if (a[i].high-a[j].high>max_high) dp[i][0]=INF;
                else
                {
                    int t1=a[i].left-a[j].left+a[i].high-a[j].high+dp[j][0];
                    int t2=a[j].right-a[i].left+a[i].high-a[j].high+dp[j][1];
                    dp[i][0]=min(t1,t2);
                }
            }
            else
            {
                if (a[i].high>max_high) dp[i][0]=INF;
                else dp[i][0]=a[i].high;
            }

            for (j=i+1; j<=n; j++)
                if (a[j].left<=a[i].right&&a[j].right>=a[i].right)
                    break;
            if (j<=n)
            {
                if (a[i].high-a[j].high>max_high) dp[i][1]=INF;
                else
                {
                    int t1=a[i].right-a[j].left+a[i].high-a[j].high+dp[j][0];
                    int t2=a[j].right-a[i].right+a[i].high-a[j].high+dp[j][1];
                    dp[i][1]=min(t1,t2);
                }
            }
            else
            {
                if (a[i].high>max_high) dp[i][1]=INF;
                else dp[i][1]=a[i].high;
            }
        }
        printf ("%d\n",min(dp[0][0],dp[0][1]));
    }
    return 0;
}

POJ 1661 动态规划 Help Jimmy

原文：http://www.cnblogs.com/nj-czy/p/5414825.html