亚洲&

zoj 3211 Dream City

The 6th Zhejiang Provincial Collegiate Programming Contest 的J題比賽的時(shí)候少考慮了一個(gè)排序..DP狀態(tài)都出來了居然還是少考慮一個(gè)情況..

6題與7題的差距是一個(gè)天一個(gè)地哎....

dp[i][j] 表示前i顆樹第j天可達(dá)到的最大值

#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個(gè)第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 米游閱讀(640) 評(píng)論(0) 編輯收藏引用所屬分類: ACM

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 有道難題... zoj 3211 Dream City 09.5.23 退役感言 RMQ ST算法 (區(qū)間最大(最小)值問題) 使用后綴數(shù)組解決zoj 3199 Longest Repeated Substring 線段樹求矩形覆蓋的周長(zhǎng) pku 1177 hdu 2816 即老菜鳥杯的1008題目 hdu 2813 即老菜鳥杯 1005題 hdu 2812 即老菜鳥杯 1004 hdu 2811 即老菜鳥杯 1003

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

ACM大牛

計(jì)算機(jī)圖形學(xué)

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜