注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

keky的博客

GAIN CONFIDENCE _=_!既然选择了远方,便只顾风雨兼程^_^

 
 
 

日志

 
 

HOJ1402 整数划分  

2007-07-13 12:24:30|  分类: cs_acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

交了老多次都WA !结果发现是数组没初始化------so a fool!

输入n, m;

第一行: 将n划分成若干正整数之和的划分数。
第二行: 将n划分成m个正整数之和的划分数。
第三行: 将n划分成最大数不超过m的划分数。
第四行: 将n划分成若干奇正整数之和的划分数。
第五行: 将n划分成若干不同整数之和的划分数。

综上可知第一、三、四、五均可用硬币找零问题决 

pp[i][j] = pp[i][j-i] + pp[i-1][j];   pp[0] = 1;

i 表示前 i 种硬币,j 表钱数;

第一:表硬币面值为1->n、 数量为无穷 的分法数;

for( i = 1; i <= n ; i++)

      for( j = n; j  >= i; j--)

         for( k = 1; ; k++)

          {

              if( k * i <= j) p1[j] += p1[j-i*k];

             else break; 

          }

第三:硬币面值为1->m、数量无穷的分法数; 同上i <= n -> i <= m;

第四:硬币面值为1 -> n 的奇数、数量无穷的分法数

for( i = 1; i <= n; i += 2)
for( j = n; j >= i; j-- )
      for( k = 1; ; k++)
  {
    if( k * i <= j) p4[j] += p4[j-k*i];
                else break;
}   
 

第五:硬币面值为1->n、每种硬币各一个的分法数;

for( i = 1; i <= n; i++)
    for( j = n; j >= i; j--)
    {
         if( j >= i )  p5[j] += p5[j-i];
        else break
    }

第二问:由于寡人人力有限故参考前辈的做法: total即为分法数。

void divide(int n, int k, int min, int index)
{
    while(min <= n/k)
{
        if(k > 1)
{
            a[index] = min;
            divide(n-min, k-1, min, index+1);
        }
        else
{
            a[index]=n;
            total++;
            return;
        }
        min++;
    }
}

希望大家多多指教!!

  评论这张
 
阅读(76)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017