pku 3585 Hurry Plotter DP

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

posted on 2010-10-14 17:48 yzhw 阅读(161) 评论(0)  编辑 收藏 引用 所属分类: DP


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2024年12月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜