狠狠狠色丁香婷婷综合久久五月,久久免费国产精品1,国产精品一二三

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 米游閱讀(652) 評論(0) 編輯收藏引用所屬分類: ACM

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 有道難題... 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 博問 Chat2DB 管理

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

ACM大牛

計算機圖形學

搜索

最新評論

閱讀排行榜

評論排行榜