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

            這個題就是一個dp問題
            我們用data[i][j]表示前i個數字構成j的方案數
            這樣的話可以得到狀態轉移方程
            data[i][j]=data[i-1][j-i]+data[i-1][j];
            邊界條件就是當j等于0的時候data[i][j]=1;
            當i等于0的時候j不等于0data[i][j]=0;
            然后提交的時候忘記測39這個數據了造成wa了一次
            因為求出來的是需要除2的
            而39這個數據的答案乘以2以后超過了int
            在計算過程中用int64或是unsigned int都是可以的。
            我選用了unsigned int這個
            因為對g++的int64用哪個一直比較混亂
            記得以前寫是用long long最近又聽說用__int64

             1/*
             2ID: bnugong1
             3PROG: subset
             4LANG: C++
             5*/

             6#include<stdio.h>
             7#include<string.h>
             8unsigned int data[40][800];
             9void di(int i,int j)
            10{
            11    unsigned int ans;
            12    if(j==0){
            13        data[i][j]=1;
            14        return;
            15    }

            16    if(i==0){
            17        data[i][j]=0;
            18        return;
            19    }

            20    if(data[i-1][j]==(unsigned int)-1)di(i-1,j);
            21    ans=data[i-1][j];
            22    if(j-i>=0){
            23        if(data[i-1][j-i]==(unsigned int)-1)di(i-1,j-i);
            24        ans+=data[i-1][j-i];
            25    }

            26    data[i][j]=ans;
            27//    printf("%d\n",ans);
            28    return;
            29}

            30int main()
            31{
            32    int n,sum;
            33    freopen("subset.in","r",stdin);
            34    freopen("subset.out","w",stdout);
            35    scanf("%d",&n);
            36    sum=((n+1)*n)/2;
            37    if(sum%2==1)printf("0\n");
            38    else
            39    {
            40        memset(data,-1,sizeof(data));
            41        sum=sum/2;
            42        di(n,sum);
            43        printf("%u\n",data[n][sum]/2);
            44    }

            45    return 0;
            46}

            47

            posted on 2008-07-19 02:58 gong 閱讀(908) 評論(0)  編輯 收藏 引用

            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            導航

            統計

            常用鏈接

            留言簿(6)

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            評論排行榜

            久久91精品综合国产首页| 欧美伊人久久大香线蕉综合69| 蜜臀av性久久久久蜜臀aⅴ | 亚洲精品乱码久久久久久不卡| 亚洲七七久久精品中文国产| 久久99国产综合精品女同| 久久久久人妻一区精品| 国产精品青草久久久久婷婷| 伊人久久大香线蕉无码麻豆| 久久本道伊人久久| 性做久久久久久免费观看| MM131亚洲国产美女久久| 久久人人青草97香蕉| 久久99精品国产麻豆蜜芽| 日韩精品无码久久久久久| 亚洲欧美日韩久久精品| 久久久精品国产Sm最大网站| 国产精品久久久久久一区二区三区| 欧美亚洲国产精品久久久久| www亚洲欲色成人久久精品| 久久久久女人精品毛片| 久久婷婷国产剧情内射白浆 | 久久久久亚洲AV片无码下载蜜桃| 久久久久国产一区二区三区| 国产精品久久永久免费| 久久国产精品成人影院| 一本一道久久综合狠狠老| 少妇熟女久久综合网色欲| 亚洲欧美一区二区三区久久| 香港aa三级久久三级老师2021国产三级精品三级在 | 国产人久久人人人人爽| 欧美日韩久久中文字幕| 一本久久免费视频| 久久婷婷五月综合国产尤物app| 亚洲国产成人精品无码久久久久久综合| 97久久精品人人做人人爽| 免费精品99久久国产综合精品| 国产精品久久久天天影视| 曰曰摸天天摸人人看久久久| 91久久九九无码成人网站| 久久精品亚洲精品国产欧美|