竹園論壇

標題: b232 - TOI2009 第四題：分房子 [打印本頁]

作者: Sylveon 時間: 2014-5-18 21:53
標題: b232 - TOI2009 第四題：分房子
原題：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());
      }
}
}

歡迎光臨竹園論壇 (http://forum.tfcis.org/)