首页 > ACM题库 > HDU-杭电 > HDU 3249-Selecting Frames-动态规划-[解题报告]HOJ
2014
03-13

HDU 3249-Selecting Frames-动态规划-[解题报告]HOJ

Selecting Frames

问题描述 :

Given n frames of unit width, your task is to select as many frames as possible and arrange them in a line, so that none of them overlap (one enclosing another is also forbidden, but merely touching is ok).

There is a restriction, though. If you select the i-th frame, you must install a small pole at Pi, then place the i-th frame surrounding that pole (the pole is so small that it can be located on the frame border). You can place the frame anywhere, as long as the pole is inside it or on its border.

输入:

There are at most 10 test cases. Each case begins with a single integer n, the number of frames (1 <= n <= 10000). Each of the following lines contains two integers Li and Pi(1 <= Li, Pi <= 100000), the length of the i-th frame, and the position of the pole associated with that frame. No two poles will have the same position. The input ends with n = 0.

输出:

There are at most 10 test cases. Each case begins with a single integer n, the number of frames (1 <= n <= 10000). Each of the following lines contains two integers Li and Pi(1 <= Li, Pi <= 100000), the length of the i-th frame, and the position of the pole associated with that frame. No two poles will have the same position. The input ends with n = 0.

样例输入:

7
5 9
2 17
6 10
3 11
2 16
4 13
5 6
0

样例输出:

5

题意:给你N个线段,每个线段有一个自己pole,要选择尽量多的线段。

满足 1.线段之间没有相交区间,但是可以紧贴着。

         2.当选择了第i个线段时,必须让第i个的线段的pole在第i个线段上。(实际上就是规定了线段放置的区间)

解题:

DP[i]表示选择了i个线段时,右端点的坐标。

每次有选或者不选2种决策,所以得到方程

dp[top]=min( dp[top] , a[i].p>=dp[top-1]+a[i].l?a[i].p:dp[top-1]+a[i].l);

选择的时候会遇到2种情况,如图:

Selecting Frames

第一种右端点放在6的位置,第二种右端点在8的位置。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define inf 0x3f3f3f3f
struct node
{
    int l;
    int p;
}a[10005];
bool cmp(node b,node c)
{
    return b.p<c.p;
}
int dp[10005];

int search(int k)
{
    for(int i=1;i<=k;i++)
    {
        if(a[k].p<dp[i])
        return i-1;
    }
}
int main()
{
    int n;
    while(scanf("%d",&n)&&n)
    {
        for(int i=1;i<=n;i++)
            scanf("%d%d",&a[i].l,&a[i].p);
        sort(a+1,a+1+n,cmp);                //根据pole位置升序
        memset(dp+1,0x3f,sizeof(int)*(n+1));
        dp[0]=-inf;
        int top=0;
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            top=search(i);  //找到第i个线段影响的top,例如样例的5 9,6 10,都会影响到dp[2]
                            
            dp[top+1]=min(dp[top+1],a[i].p>=dp[top]+a[i].l?a[i].p:dp[top]+a[i].l);  //通过转移方程找到最优解
            if(top+1>ans)   //记录答案
            ans=top+1;
        }

        printf("%d\n",ans);
    }
    return 0;
}

参考:http://blog.csdn.net/t1019256391/article/details/9089317


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience