b232 - TOI2009 第四題：分房子

Sylveon

原題：http://zerojudge.tw/ShowProblem?problemid=b232
AC：http://zerojudge.tw/Submissions? ... mp;account=lfs92002

本題DP+大數。大數隨便抓個以前的模板就解決了。我都忘記我怎麼DP了，這是一年前寫的CODE，沒什麼印象，不過看起來就是背包。


/**********************************************************************************/
/*  Problem: b232 "TOI2009 第四題：分房子" from 2009 TOI 研習營初選   */
/*  Language: CPP (2389 Bytes)                                                    */
/*  Result: AC(0.3s, 161.7MB) judge by this@ZeroJudge                             */
/*  Author: lfs92002 at 2013-02-25 14:17:42                                       */
/**********************************************************************************/


#include<cstdio>
#include<string.h>
#include<iostream>
using namespace std;

class bigNum{
    int tmp[50];
    public:
        char data[50];
        char p[50];
        bigNum()
        {
            int t=0;
            while(t<50)data[t++]='\0';
        }
        bigNum& operator=(int num)
        {
            int t=0;
            while(num)
            {
                data[t]=num%10+'0';
                t++;
                num/=10;
            }
            while(t<50)data[t++]='\0';
            return *this;
        }
        bigNum operator+(const bigNum &a)
        {
            bigNum g;
            for(int i=0;i<50;i++)
            {
                g.tmp[i]=0;
                if(data[i]>'0')g.tmp[i]+=data[i]-'0';
                if(a.data[i]>'0')g.tmp[i]+=a.data[i]-'0';
            }
            for(int i=0;i<50-1;i++)
            {
                if(g.tmp[i]>9)
                {
                    g.tmp[i+1]+=g.tmp[i]/10;
                    g.tmp[i]%=10;
                }
                g.data[i]='0'+g.tmp[i];
            }
            int t=50-1;
            while(g.data[t]=='0')g.data[t--]='\0';
            return bigNum(g);
        }
        char * print()
        {
            memset(p,0,sizeof(p));
            int L=strlen(data)-1,d=0;
            while( L>=0 &&data[L]=='0') L--;
            while( L>=0 ) p[d++]=data[L--];
            return p;
        }
        
};

bigNum dp[751][751];
int main()
{
    memset(dp,0,sizeof(dp));
    dp[0][0]=dp[0][0]=1;
    int N,T,i_line,D;
    while(~scanf("%d",&T))
    {
        while(T--)
        {
            scanf("%d",&N);
            i_line=(N+1)/2;
            for(int i=1;i<=i_line;i++)
            {
                for(int j=0;j<=N;j++)
                {
                    D=i*2-1;
                    if(D>j)
                    {
                        dp[i][j]=dp[i-1][j];
                    }
                    else
                    {
                        dp[i][j]=dp[i-1][j]+dp[i][j-D];
                    }
                }
            }
            printf("%s\n",dp[i_line][N].print());
        }
    }
}