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

zjushuiping

追求的只是心中的那一份宁静!

 
 
 

日志

 
 

2012年01月31日  

2012-01-31 22:28:14|  分类: ACM/ICPC |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

hdoj 2069  http://acm.hdu.edu.cn/showproblem.php?pid=2069

 

 

方法一:暴力法

由于数据规模不是很大,可以考虑用暴力穷举的方法:

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

int main()
{

 int i,j,k,g,h;

 int sum[251];


 for(i=0;i<=250;i++)
  sum[i]=0;


 for(i=0;i<=100;i++)
  for(j=0;j<=50;j++)
  {if(i+j>100)
   break;
  if(i*1+j*5>250)
   break;
  for(k=0;k<=25;k++)
  {if(i+j+k>100)
  break;
  if(i*1+j*5+k*10>250)
   break;
  for(g=0;g<=10;g++)
  {if(i+j+k+g>100)
  break;
  if(i*1+j*5+k*10+g*25>250)
   break;
  for(h=0;h<=5;h++)
  {if(i+j+k+g+h>100)
   break;
  if(i*1+j*5+k*10+g*25+h*50>250)
   break;
  sum[i*1+j*5+k*10+g*25+h*50]++;
  }
  }
  }
  }


 int n;

 while(~scanf("%d",&n))
 {
  cout<<sum[n]<<endl;
 }

 return 0;
}

 

 

方法二:

本题也可以考虑用母函数,只是这题比一般的母函数要复杂一点:
c[i][j]表示i分的钱用j枚硬币表示有才c[i][j]种方法.

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <stack>
#include <vector>


using namespace std;

int c1[251][101],c2[252][101];
int v[5]={1,5,10,25,50};

//50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We
   
int main()
{
 
int n;
int i,j,k,g,h;

int sum[251];

for(i=0;i<=250;i++)
{sum[i]=0;
for(j=0;j<=100;j++)
{
                   c1[i][j]=c2[i][j]=0;
}
}


for(i=0;i<=100;i++)
c1[i][i]=1;

for(i=1;i<5;i++)
{ for(j=0;j<=250;j++)
 {
                    for(k=0;k*v[i]+j<=250;k++)
                    {
                                              for(g=0;k+g<=100;g++)
                                              {
                                                                 c2[j+k*v[i]][g+k]+=c1[j][g];
                                              }
                    }
 }
 for(j=0;j<=250;j++)
 for(k=0;k<=100;k++)
 {c1[j][k]=c2[j][k];c2[j][k]=0;}
 
 
}

for(i=0;i<=250;i++)
for(j=0;j<=100;j++)
{
                   sum[i]+=c1[i][j];
}
while(~scanf("%d",&n))
{
                      cout<<sum[n]<<endl;
}


                                                                                                   
system("PAUSE");

                      
                            
                     
return 0;
}

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

历史上的今天

评论

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

页脚

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