亚洲精品美女久久7777777,欧美日韩美女,国产亚洲欧美aaaa

[動(dòng)態(tài)規(guī)劃]pku1050

枚舉矩形的上邊和下邊，花費(fèi)O(n²)，把問題轉(zhuǎn)化成一維的最大M子段和，做一個(gè)O(n)的DP。

#include <stdio.h>

const int maxint = 2147483647;

int max(int n, int *a)

{

int sum = -maxint, b = 0;

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

{

if (b > 0)

b += a[i];

else

b = a[i];

sum >?= b;

}

return sum;

}

int a[101][101];

int maxsum(int n)

{

int sum = -maxint, *b = new int[n + 1];

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

{

for (int j = 1; j <= n; j++)

b[j] = a[i][j];

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

{

for (int k = 1; k <= n; k++)

b[k] += a[j][k];

sum >?= max(n, b);

}

return sum;

}

int main()

{

int n;

scanf("%d", &n);

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

for (int j = 1; j <= n; j++)

scanf("%d", &a[i][j]);

printf("%d\n", maxsum(n));

return 0;

}

posted on 2007-08-26 13:51 Felicia 閱讀(1044) 評(píng)論(6) 編輯收藏引用所屬分類: 動(dòng)態(tài)規(guī)劃

Comments

# re: [動(dòng)態(tài)規(guī)劃]pku1050
@潘帕斯雄鷹
Posted @ 2007-08-30 23:16
大牛天天更新，小菜一定天天過來踩回復(fù) 更多評(píng)論
# re: [動(dòng)態(tài)規(guī)劃]pku1050
Gchris
Posted @ 2007-12-07 16:28
大牛同學(xué),你好!
為什么你的blog里有 sum >?= max(n, b); 這樣的語句,是不是blog系統(tǒng)出錯(cuò)了? 回復(fù) 更多評(píng)論
# re: [動(dòng)態(tài)規(guī)劃]pku1050
Felicia
Posted @ 2007-12-07 20:07
我不是大牛。
blog系統(tǒng)沒錯(cuò)，>?=是運(yùn)算符回復(fù) 更多評(píng)論
# re: [動(dòng)態(tài)規(guī)劃]pku1050
Gchris
Posted @ 2007-12-08 23:25
@Felicia
可是我把它拷到 VC 里不能運(yùn)行
回復(fù) 更多評(píng)論
# re: [動(dòng)態(tài)規(guī)劃]pku1050
Gchris
Posted @ 2007-12-08 23:28
>?=
是什么意思？回復(fù) 更多評(píng)論
# re: [動(dòng)態(tài)規(guī)劃]pku1050
Felicia
Posted @ 2007-12-10 21:23
……不要用VC編譯，用G++編譯回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊用戶登錄后才能發(fā)表評(píng)論。


相關(guān)文章: [動(dòng)態(tài)規(guī)劃]O(n^2 / logn)的LCS [動(dòng)態(tài)規(guī)劃] pku1458 最長公共子序列 [動(dòng)態(tài)規(guī)劃]pku1080 [動(dòng)態(tài)規(guī)劃]pku1338 [動(dòng)態(tài)規(guī)劃]pku3420 [動(dòng)態(tài)規(guī)劃]pku1191 [動(dòng)態(tài)規(guī)劃]pku1179 [動(dòng)態(tài)規(guī)劃]pku1189 [動(dòng)態(tài)規(guī)劃]pku1185 [動(dòng)態(tài)規(guī)劃]pku1163

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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

導(dǎo)航

常用鏈接

留言簿(22)

隨筆分類(145)

隨筆檔案(149)

相冊

ACMers

Pretty Girls

最新隨筆

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜