Summary
给出N(N<=1000)个需要绘制的平行于X轴的线段，知道其坐标，以(Y,X1,X2)表示。有一绘图仪，从Y=0位置开始绘制这些线段。对于同一个Y，绘图仪可以从X=x1到X=x2，平移时耗费时间|x2-x1|，绘制线段则耗费双倍时间2|x2-x1|。但是，在垂直方向上，绘图仪只能从y1移动到y2，y1<y2，且此时X必须=0。线段的绘制必须是完整的，不能只绘制一半。现问：绘图仪在规定的之间T内最多能绘制多少条线段。
Solution
使用动态规划可以解决这个问题。
设DP状态为：dp[i][j]，表示绘制到第i个线段（这个线段必须绘制），绘制了j个线段，所需要的最少时间。那么dp[i][j] = min(dp[k][j-1] + dis(segment[i], segment[k]) + time to draw segment[i]。dis表示两个线段的“距离”，分情况讨论计算即可。
最后统计所有时间小于等于T的方案取出最优的即可。
注意灵活选择状态，用范围小的作为状态量，将范围大的选作为状态值
1
# include <iostream>
2# include <cstring>
3# include <cstdio>
4# include <algorithm>
5using namespace std;
6struct node
7
{
8
int y,x1,x2;
9
}data[1005];
10bool cmp(const node &a,const node &b)
11{
12 if(a.y!=b.y) return a.y<b.y;
13 else return a.x1<b.x1;
14}
15int dp[1005][1005];
16int main()
17{
18 int n,t;
19 while(true)
20
{
21 scanf("%d%d",&n,&t);
22 if(!n&&!t) break;
23 for(int i=0;i<n;i++)
24 {
25 scanf("%d%d%d",&data[i].y,&data[i].x1,&data[i].x2);
26 if(data[i].x1>data[i].x2) swap(data[i].x1,data[i].x2);
27
}
28 sort(data,data+n,cmp);
29 int res=0;
30 memset(dp[0],0,sizeof(dp[0]));
31 for(int i=0;i<n;i++)
32 {
33 dp[1][i]=(data[i].x2-data[i].x1)*3+data[i].x1*2;
34 if(dp[1][i]-data[i].x2<=t)
35 res=1;
36 }
37 for(int i=1;i<n;i++)
38 {
39 for(int j=2;j<=i+1;j++)
40 {
41 dp[j][i]=0xfffffff;
42 for(int k=j-2;k<i;k++)
43 dp[j][i]=min(dp[j][i],dp[j-1][k]+(data[k].y==data[i].y?(data[i].x1-data[k].x2)*2+(data[i].x2-data[i].x1)*3:data[i].x1*2+3*(data[i].x2-data[i].x1)));
44 if(dp[j][i]-data[i].x2<=t)
45 res=max(res,j);
46 }
47 }
48 printf("%d\n",res);
49 }
50 return 0;
51}
52