• <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>

            USACO 2.2 Subset Sums

            動(dòng)態(tài)規(guī)劃經(jīng)典題子集和問題。
            求子集和為總數(shù)的一半的子集的個(gè)數(shù),按題意,還要再除以2。
            int會(huì)溢出,要用long long.第一次提交就沒有注意到這個(gè)問題。


            #include?
            <iostream>
            #include?
            <fstream>

            using?namespace?std;

            ifstream?fin(
            "subset.in");
            ofstream?fout(
            "subset.out");

            #ifdef?_DEBUG
            #define?out?cout
            #define?in?cin
            #else
            #define?out?fout
            #define?in?fin
            #endif

            long?long?dp[800];

            void?solve()
            {

            ????
            int?n;
            ????
            in>>n;

            ????
            int?sum?=?(n+1)*n/2;

            ????
            if(sum&1){
            ?????? //和為奇數(shù),無解
            ????????out<<0<<endl;
            ????????
            return;
            ????}

            ????sum
            >>=1;


            ????dp[
            0]?=?1;

            ????
            for(int?i=1;i<=n;++i){
            ????????
            //從后向前,空間復(fù)雜度就降為O(n)了,具體可參考<背包問題九講>
            ????????for(int?t?=?sum;t>=i;--t){
            ????????????dp[t]
            +=dp[t-i];
            ????????}
            ????}

            ????
            out<<dp[sum]/2<<endl;
            }

            int?main(int?argc,char?*argv[])
            {
            ????solve();?
            ????
            return?0;
            }


            posted on 2009-06-20 17:25 YZY 閱讀(1693) 評(píng)論(0)  編輯 收藏 引用 所屬分類: AlgorithmUSACO

            導(dǎo)航

            <2009年6月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            統(tǒng)計(jì)

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評(píng)論

            閱讀排行榜

            久久综合亚洲色HEZYO社区| 97精品国产91久久久久久| 精品午夜久久福利大片| 香蕉久久av一区二区三区| 亚洲欧洲久久av| 精品久久久久久久久免费影院| 久久午夜福利电影| 久久久国产视频| 久久久久亚洲AV无码专区首JN| 久久强奷乱码老熟女网站| A级毛片无码久久精品免费| 久久午夜福利无码1000合集| 久久亚洲精品无码VA大香大香| 东方aⅴ免费观看久久av| 浪潮AV色综合久久天堂| 1000部精品久久久久久久久| 亚洲乱亚洲乱淫久久| 久久精品国产清自在天天线| 久久影视综合亚洲| 久久亚洲精品人成综合网| 久久久久夜夜夜精品国产| 久久精品成人欧美大片| 国产69精品久久久久APP下载| 伊人久久大香线蕉av不变影院| 久久精品水蜜桃av综合天堂| 99久久综合狠狠综合久久| 久久成人小视频| 99热成人精品热久久669| 久久伊人色| 国内精品久久人妻互换| 久久久久国产精品麻豆AR影院| 亚洲国产欧洲综合997久久| 99久久国产免费福利| 久久精品国产欧美日韩99热| 国内精品久久久久伊人av| 欧美久久一区二区三区| 久久精品一区二区| 国产精品久久久久久久app | 九九精品99久久久香蕉| 国内精品久久久久久不卡影院| 久久精品国产亚洲av麻豆蜜芽|