首页 > 其他 > 详细

Ignatius and the Princess III HDU - 1028 -生成函数or完全背包计数

时间:2019-01-13 01:18:26      阅读:183      评论:0      收藏:0      [点我收藏+]

 HDU - 1028 

step 1:初始化第一个多项式 也就是 由 1的各种方案 组 成 的多项式 初始化系数为 1。临时区 temp初始化 为 0

step 2:遍历后续的n - 1 个 多项式 ,第二重 for  j  代 表 的 存 储 结 果 的 多 项 式的次数,k 代表 当前 第 i 的 多项式的次数

通过计算发现两个多项式相乘 其中一个 系数为1和 0 组成,运算时可以初始化系数数组为0 ,然后 由另一个的系数 与之相加即可得到     

G(x)=(1+x+x2+x3+x4+.....)(1+x2+x4+x6+x8+......)(1+x3+x6+x9+....)........(1+xn)

#include<bits/stdc++.h>
using namespace std;
#define maxn 234
int ans[maxn],tp[maxn],n;
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=0; i<=n; i++)
            ans[i]=1,tp[i]=0;
        for(int i=2; i<=n; i++)
        {
            for(int j=0; j<=n; j++)
                for(int k=0; k+j<=n; k+=i)
                    tp[j+k]+=ans[j];
            for(int j=0; j<=n; j++)
                ans[j]=tp[j],tp[j]=0;
        }
        printf("%d\n",ans[n]);
    }
    return 0;
}

  

Ignatius and the Princess III HDU - 1028 -生成函数or完全背包计数

原文:https://www.cnblogs.com/SDUTNING/p/10261600.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!