中文字幕日本人妻久久久免费,精品国产热久久久福利,色婷婷久久综合中文久久蜜桃av

[動態規劃]pku1050

枚舉矩形的上邊和下邊，花費O(n²)，把問題轉化成一維的最大M子段和，做一個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 閱讀(1026) 評論(6) 編輯收藏引用所屬分類: 動態規劃

Comments

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

刷新評論列表

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

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

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

導航

常用鏈接

留言簿(21)

隨筆分類(145)

隨筆檔案(149)

相冊

ACMers

Pretty Girls

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜