Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 3014 Cake Pieces and Plates---整数划分

Posted on 2009-08-24 20:14 Uriel 阅读(236) 评论(0)  编辑 收藏 引用 所属分类: POJ
/*Problem: 3014  User: Uriel 
  Memory: 68100K  Time: 4657MS 
  Language: GCC  Result: Accepted*/ 

#include<stdio.h>

int i,j,m,n,dp[4600][4600],k;
int main()
{
    scanf("%d %d",&m,&n);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(i==1 || j==1)dp[i][j]=1;
            else if(i<j)
            {
                for(k=j;k<=m;k++)
                {
                    dp[i][k]=dp[i][i];
                    break;
                }
            }
            else if(i==j)dp[i][j]=(dp[i][j-1]%1000000007+1)%1000000007;
            else 
                dp[i][j]=(dp[i][j-1]%1000000007+dp[i-j][j]%1000000007)%1000000007;
        }
    }
    printf("%d\n",dp[n][m]);
    return 0;
}
抄王晓东书过的。。用memset超时。。去掉就过了，不过Memory 和 Time都。。。。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理