2014
03-13

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

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

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

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

#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;
}

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