Summary
給出N(N<=1000)個(gè)需要繪制的平行于X軸的線段，知道其坐標(biāo)，以(Y,X1,X2)表示。有一繪圖儀，從Y=0位置開始繪制這些線段。對(duì)于同一個(gè)Y，繪圖儀可以從X=x1到X=x2，平移時(shí)耗費(fèi)時(shí)間|x2-x1|，繪制線段則耗費(fèi)雙倍時(shí)間2|x2-x1|。但是，在垂直方向上，繪圖儀只能從y1移動(dòng)到y(tǒng)2，y1<y2，且此時(shí)X必須=0。線段的繪制必須是完整的，不能只繪制一半。現(xiàn)問：繪圖儀在規(guī)定的之間T內(nèi)最多能繪制多少條線段。
Solution
使用動(dòng)態(tài)規(guī)劃可以解決這個(gè)問題。
設(shè)DP狀態(tài)為：dp[i][j]，表示繪制到第i個(gè)線段（這個(gè)線段必須繪制），繪制了j個(gè)線段，所需要的最少時(shí)間。那么dp[i][j] = min(dp[k][j-1] + dis(segment[i], segment[k]) + time to draw segment[i]。dis表示兩個(gè)線段的“距離”，分情況討論計(jì)算即可。
最后統(tǒng)計(jì)所有時(shí)間小于等于T的方案取出最優(yōu)的即可。
注意靈活選擇狀態(tài)，用范圍小的作為狀態(tài)量，將范圍大的選作為狀態(tài)值
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