精品午夜久久福利大片,国产精品久久久久…,国产99精品久久

2011年3月

日

一

二

三

四

五

六

統計

隨筆 - 29
文章 - 0
評論 - 2
引用 - 0

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

閱讀排行榜

評論排行榜

雙向的動態規劃問題 POJ 2593

http://poj.org/problem?id=2593

#include<iostream>

#include<stdio.h>

const int MIN = -999999999;//定義MIN為只讀變量為一個非常小的值

int a[100001];

int ans[100001];

using namespace std;

int main()

{

int n;

int an;

while(scanf("%d",&n)!=EOF)

{

if(n==0)

break;

int sum=0;

int k=MIN;

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

{

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

sum+=a[i];

if(sum>k)

k=sum;

ans[i]=k;//第i個數前的最大連續和為ans[i]

if(sum<0)//如果sum<0 則舍棄前面的數 sum從下一個數開始加

sum=0;

}

sum=0;

k=an=MIN;

for(int j=n;j>1;j--)//反方向查找

{

sum+=a[j];

if(sum>k)

k=sum;

if(an<(ans[j-1]+k))//從后數前n-j+1個數的最大連續和k 加上正數第j-1個數的最大連續和

an=ans[j-1]+k;//用an

if(sum<0)//如果sum<0 則舍棄前面的數 sum從下一個數開始加

sum=0;

}

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

}

return 0;

}

posted on 2011-03-22 22:28 Yiner 閱讀(457) 評論(0) 編輯收藏引用所屬分類: DP

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

相關文章: POJ 1742 多重背包雙向的動態規劃問題 POJ 2593

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

Yiner的ACM

統計

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

雙向的動態規劃問題 POJ 2593