hdu 1398 普通母函数

本文主要是介绍hdu 1398 普通母函数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目传送门：点击打开链接

 这道题其实就是模版题，唯一不同的是每一项的指数不同，所以在模版里最外层的 不是i＋＋，而是1,4,9,16....17^2,i代表的是第i种硬币类型，这种类型的硬币能提供价值为i*1,i*2,i*3。。还有不懂的可以看一下代码，如果在不懂我想你可以看一下点击打开链接的博客内容。

#include <iostream>
#include <cstdio>
using namespace std;
int data[]={0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289};
int c1[1000],c2[1000];
int n;
void init()
{for(int i=0;i<=n;++i){c1[i]=1;c2[i]=0;}int cnt=2;for(int i=data[cnt];i<=n&&cnt<=17;i=data[++cnt])  //注意这里 这个代码用g++交会超时，c++不超，也可以改成 for(;cnt<=17;++cnt)   {                                                                                       //       int i=data[cnt];<span style="font-family: Arial, Helvetica, sans-serif;"> </span>for(int j=0;j<=n;++j)                                                               //        if(i>n)  break for(int k=0;k+j<=n;k+=i)c2[k+j]+=c1[j];// cout<<cnt<<": ";for(int j=0;j<=n;++j){c1[j]=c2[j],c2[j]=0;// cout<<c1[j]<<" ";}// cout<<endl;}
}
int main(int argc, const char * argv[])
{while(scanf("%d",&n)==1){if(!n)break;init();cout<<c1[n]<<endl;}return 0;
}

这篇关于hdu 1398 普通母函数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---