• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Yiner的ACM

            成長的痕跡
            <2011年3月>
            272812345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            統(tǒng)計

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

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            雙向的動態(tài)規(guī)劃問題 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個數(shù)前的最大連續(xù)和為ans[i]
                        if(sum<0)//如果sum<0 則舍棄前面的數(shù) sum從下一個數(shù)開始加
                           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))//從后數(shù)前n-j+1個數(shù)的最大連續(xù)和k 加上 正數(shù)第j-1個數(shù)的最大連續(xù)和
                         an=ans[j-1]+k;//用an
                         if(sum<0)//如果sum<0 則舍棄前面的數(shù) sum從下一個數(shù)開始加
                         sum=0;
                    }

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

                
            return 0;
            }


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

            久久久久99精品成人片欧美| 99久久夜色精品国产网站| 国产精品18久久久久久vr | 国产99久久久久久免费看| 国产99久久久国产精免费| 国产AⅤ精品一区二区三区久久| 久久久久久午夜精品| 四虎久久影院| 亚洲精品久久久www| 久久精品免费观看| 精品久久久久久久无码| 99久久国产精品免费一区二区| 亚洲精品国产成人99久久| 91久久精品91久久性色| 久久免费的精品国产V∧| 区亚洲欧美一级久久精品亚洲精品成人网久久久久 | 精品一二三区久久aaa片| 久久99精品久久久久久噜噜| 久久久久亚洲精品男人的天堂| 久久综合视频网站| 久久久精品免费国产四虎| 精品伊人久久大线蕉色首页| 99久久人人爽亚洲精品美女| 久久男人Av资源网站无码软件 | 久久久久亚洲av无码专区导航| 欧美大战日韩91综合一区婷婷久久青草| 精品无码久久久久久尤物| 99久久香蕉国产线看观香| 久久996热精品xxxx| 国产精品久久久99| 精品久久久久久99人妻| 国产91久久综合| 久久久久国产亚洲AV麻豆| 国产精品99久久不卡| 久久久青草久久久青草| 久久精品国产精品青草app| 久久精品九九亚洲精品天堂 | 99re久久精品国产首页2020| 久久偷看各类wc女厕嘘嘘| 久久久久免费看成人影片| 国产精品久久影院|