POJ 1221

1269 단어
//  :                 
//  :http://blog.csdn.net/linulysses/article/details/5820916
//           1、      2、      
//  n       ,                ,           i,         y=(n-i)/2(    ),   f(y,i)
//  n   ,                     ,f(n/2,n/2),n/2     
//11205502	c00h00g	1221	Accepted	4340K	454MS	G++	807B	2013-01-24 18:35:12
//          
//      ,POJ 1221 
//        
#include<stdio.h>
#include<stdlib.h>
#include<string.h>


int dp[1005][1005];

__int64 f(int n,int m){
    if(dp[n][m])
        return dp[n][m];
    if(n==1||m==1) return dp[n][m]=1;
    if(m>n)
        return dp[n][m]=f(n,n);
    else if(m==n)
        return dp[n][m]=f(n,m-1)+1;
    else if(m<n)
        return dp[n][m]=f(n,m-1)+f(n-m,m);
}

int n;
int main(){
    while(scanf("%d",&n)!=EOF){
        if(n==0)
            break;
        memset(dp,0,sizeof(dp));
        //  f     0   ,   res  1,         
        __int64 res=1;
        int y;
        for(int i=1;i<n;i++){
            if((n-i)%2==0){
                //       
                y=(n-i)>>1;
                res+=f(y,i); 
            }
        }
        if(n%2==0)
            res+=f(n/2,n/2);
        printf("%d %I64d
",n,res); } return 0; }

좋은 웹페이지 즐겨찾기