Sephiroth's boring days!!!

Love just for you.

数的划分-递推动态规划

又一经典问题,noip2001。

用到了分类的思想。对于f[i][j]代表i分为j份。我们分为以下两类:

  1. 每份都没有1:那么我们只需要将每份都减1然后保证有j份。即加上f[i-j][j]。
  2. 至少有一份1:那么我们提出1个1,即加上f[i-1][j-1]。
  1: #include <stdio.h>
  2: #define maxn 300
  3: 
  4: int f[maxn][maxn];
  5: int n,m;
  6: 
  7: int main()
  8: {
  9:     scanf("%d%d",&n,&m);
 10:     f[0][0]=1;
 11:     for (int i=1;i<=n;++i)
 12:         for (int j=1;j<=m;++j)
 13:             if (i-j>=0)
 14:                 f[i][j]=f[i-j][j]+f[i-1][j-1];
 15:     printf("%d\n",f[n][m]);
 16:     return 0;
 17: }
 18: 

posted on 2010-08-28 11:04 Sephiroth Lee 阅读(473) 评论(0)  编辑 收藏 引用 所属分类: 信息奥赛


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


free counters