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

            閱讀排行榜

            久久精品无码一区二区app| 国产视频久久| 国产午夜免费高清久久影院| 精品久久久久久中文字幕| 久久久无码精品亚洲日韩软件| 亚洲综合久久夜AV | 大伊人青草狠狠久久| 欧美久久天天综合香蕉伊| 国产精品一区二区久久 | 国产精品久久亚洲不卡动漫| 国产日韩久久久精品影院首页 | 成人妇女免费播放久久久| 久久天天躁狠狠躁夜夜2020| 97久久精品人妻人人搡人人玩| 欧美久久天天综合香蕉伊| 久久超碰97人人做人人爱| 婷婷国产天堂久久综合五月| 久久国产精品久久精品国产| 精品多毛少妇人妻AV免费久久| 国产精品日韩欧美久久综合| 性欧美丰满熟妇XXXX性久久久 | 国内精品九九久久久精品| 性做久久久久久久久| 国产精品美女久久久免费| 国产精品久久久久久搜索| 久久九九久精品国产免费直播| 久久久精品国产Sm最大网站| 97久久香蕉国产线看观看| 久久久久久亚洲精品成人| 性做久久久久久久| 亚洲综合熟女久久久30p| 久久精品aⅴ无码中文字字幕不卡| 久久国产高清一区二区三区| 亚洲一区二区三区日本久久九| 久久超乳爆乳中文字幕| 久久精品无码专区免费东京热| 性色欲网站人妻丰满中文久久不卡| 久久久久久久久久久久久久| 99久久精品国产一区二区| 无码人妻少妇久久中文字幕蜜桃 | 国内精品久久久久国产盗摄|