zoj 3211 Dream City

The 6th Zhejiang Provincial Collegiate Programming Contest 的J题比赛的时候少考虑了一个排序..DP状态都出来了居然还是少考虑一个情况..

6题与7题的差距是一个天一个地哎....

dp[i][j] 表示前i颗树第j天可达到的最大值

#include<iostream>
2

#include<algorithm>
3

using namespace std;
4

struct node
5

{
6

int a,b;
7

};
8

bool operator<(const node& d,const node& e)
9

{
10

return d.b<e.b;
11

}
12

node r[300];
13

int dp[300][300];
14

int main()
15

{
16

int n,m,t;
17

cin>>t;
18

while(t--)
19

{
20

cin>>n>>m;
21

for(int i=1;i<=n;i++)
22

cin>>r[i].a;
23

for(int i=1;i<=n;i++)
24

cin>>r[i].b;
25

sort(r+1,r+n+1);
26

memset(dp,0,sizeof(dp));
27

//dp[i][j] 表示前i个第j天的最大值
28

for(int i=1;i<=n;i++)
29

for(int j=1;j<=m;j++)
30

{
31

if(j>i)
32

break;
33

dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+r[i].a+r[i].b*(j-1));
34

}
35

cout<<dp[n][m]<<endl;
36

}
37

}

posted on 2009-05-25 15:35 米游阅读(609) 评论(0) 编辑收藏引用所属分类: ACM

常用链接

留言簿(1)

随笔分类

随笔档案

ACM大牛

计算机图形学

搜索

最新评论

阅读排行榜

评论排行榜

只有注册用户登录后才能发表评论。


相关文章: 有道难题... zoj 3211 Dream City 09.5.23 退役感言 RMQ ST算法 (区间最大(最小)值问题) 使用后缀数组解决zoj 3199 Longest Repeated Substring 线段树求矩形覆盖的周长 pku 1177 hdu 2816 即老菜鸟杯的1008题目 hdu 2813 即老菜鸟杯 1005题 hdu 2812 即老菜鸟杯 1004 hdu 2811 即老菜鸟杯 1003

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理