>您写了一个暴力背包DP能不TLE吗?
by Reaepita @ 2018-10-28 11:44:53
这个代码,跟母函数没关系吧
by Reaepita @ 2018-10-28 11:45:25
@[Harry_bh](/space/show?uid=19951) 我这就是母函数的模板,不过是用的dp函数名而已。睿智
by Zroom @ 2018-11-07 13:43:40
@[zhangjunhuai](/space/show?uid=84095) 你这个不是DP我倒立女装,睿智吧你
by Reaepita @ 2018-11-07 14:40:12
思想是母函数,代码本质和DP没有区别
by Reaepita @ 2018-11-07 14:46:55
您可写一个FFT,不然稳定TLE
by Reaepita @ 2018-11-07 14:48:17
来,现在我给你手推一个dp方程
by Reaepita @ 2018-11-07 14:48:47
```cpp
通用模板
下面我直接给出通用模板:
//为计算结果,b为中间结果。
int a[MAX],b[MAX];
//初始化a
memset(a,0,sizeof(a));
a[0]=1;
for (int i=1;i<=17;i++)//循环每个因子
{
memset(b,0,sizeof(b));
for (int j=n1[i];j<=n2[i]&&j*v[i]<=P;j++)//循环每个因子的每一项
for (int k=0;k+j*v[i]<=P;k++)//循环a的每个项
b[k+j*v[i]]+=a[k];//把结果加到对应位
memcpy(a,b,sizeof(b));//b赋值给a
}
P是可能的最大指数。拿钞票组合这题来说,如果要求15元有多少组合,那么P就是15;如果问最小的不能拼出的数值,那么P就是所有钱加起来的和。P有时可以直接省略。具体请看本文后面给出的例题。
如果n2是无穷,那么第二层循环条件j<=n2[i]可以去掉。
---------------------
作者:小飞_Xiaofei
来源:CSDN
原文:https://blog.csdn.net/xiaofei_it/article/details/17042651
版权声明:本文为博主原创文章,转载请附上博文链接!
```
by Zroom @ 2018-11-07 14:51:23
没错啊,我都说了
>思想是母函数,代码本质和暴力DP没有区别
by Reaepita @ 2018-11-07 14:52:28
@[Harry_bh](/space/show?uid=19951) 随便你...,那个”睿智“是我过激了
by Zroom @ 2018-11-07 14:52:51