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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1085  

2012-03-25 05:55:57|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

母函数,照着模板过了~

后来看了别人的解题报告,竟然可以暴力过,还可以找规律过哦~~

1.暴力方法O(n^3)

#include <iostream>
using namespace std;
int main()
{
    int a[10000],n1,n2,n3,i,j,k,sum;
    while(scanf("%d%d%d",&n1,&n2,&n3))
    {
        if(n1==0&&n2==0&&n3==0) break;
        n2 *= 2;
        n3 *= 5;
        sum = n1+n2+n3;
        for(i=0;i<=sum;i++)
            a[i]=0;
        for(i=0;i<=n1;i++)
            for(j=0;j<=n2;j+=2)
                for(k=0;k<=n3;k+=5)
                    a[i+j+k]=1;
        for(i=1;i<=sum;i++)
            if(a[i]==0)
                break;
        printf("%d\n",i);
    }
    return 1;
}

2.母函数法

#include<stdio.h>
int a[8001],b[8001];
int c[]={1,2,5};
int main()
{
    int i,j,k,n[3],s;
    while(scanf("%d%d%d",&n[0],&n[1],&n[2])!=EOF,n[0]+n[1]+n[2])
    {
        s = n[0]*1 + n[1]*2 + n[2]*5;
        if(n[0]==0)printf("1\n");
        else
        {
            for(i=0; i<8001; i++)
            {
                b[i]=0;
                a[i]=0;
            }
            for(i=0; i<=n[0]; i++)
            {
                a[i]=1;
            }
            for(i=1; i<3; i++)
            {
for(j=0; j<=s; j++)
                {
                    for(k=0; k*c[i]+j<=s && k<=n[i]; k++)
                    {
                        b[k*c[i]+j]+=a[j];
                    }
                }
                for(j=0; j<=s; j++)
                {
                    a[j]=b[j];
                    b[j]=0;
                }
            }
            for(i=0; i<=s+1; i++)
            {
                if(a[i]==0)
                {
                    printf("%d\n",i);
                    break;
                }
            }
        }
    }
    return 0;
}

3.找规律

#include<stdio.h>
int main()
{
    int i,j,k,n1,n2,n5;
    while(scanf("%d%d%d",&n1,&n2,&n5)!=EOF,n1+n2+n5)
    {
        if(n1==0)printf("1\n");
        else if(n1+n2*2<4)printf("%d\n",n1+n2*2+1);
        else printf("%d\n",n1+n2*2+n5*5+1);
    }
    return 0;
}

参考来自:http://apps.hi.baidu.com/share/detail/6310659

 

 

母函数(模板):

# include <stdio.h>
# include <string.h>


int dp[10000] ;
int buf[10000] ;


void Generation(int num[], int value[], int n, int max_value)
{
int i, j, k ;
for (dp[0] = 1, i = 1 ; i <= max_value ; i++)
dp[i] = 0 ;
//开始乘
for (k = 0 ; k < n ; k++)
{
for (i = 0 ; i <= max_value ; i++) buf[i] = 0 ;
for (i = 0 ; i <= num[k] * value[k] ; i+= value[k]) // 1 + x^value[i] + x^{value[i] * 2} + ...
{
for (j = 0 ; j + i <= max_value ; j++)
buf[j + i] += dp[j] ;
}
for (i = 0 ; i <= max_value ; i++)
dp[i] = buf[i] ;
}
}


int main ()
{
int n[3], value[3] = {1, 2, 5} ;
int i, max_value ;
while (~scanf ("%d%d%d", &n[0], &n[1], &n[2]))
{
if (n[0] == 0 && n[1] == 0 && n[2] == 0) break ;
max_value = n[0] + n[1] * 2 + 5 * n[2] ;
Generation (n, value, 3, max_value) ;
for (i = 0 ; i <= max_value ;i++)
if (dp[i] == 0) break ;
printf ("%d\n", i) ;
}
return 0 ;
}

 

 

  评论这张
 
阅读(372)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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