邮票（完全背包）

· · 个人记录

邮票 stamp

题目有k\le200个位置，m\le50种面值，面值最大小于10000 如果像完全背包那么枚举，N^3，肯定是T了（为什么我还WA了qwq。。。），再一个就是数组要开到maxm*k。完全背包优化方式之一见飞扬的小鸟

在这里的枚举方式是先枚举点，然后枚举可以转移到它的点，将f[j-a[i]]+1与f[j]比较。就只用枚举点和面值了。

while(f[i]<=n)
{
    i++;
    for(int j=1;j<=m;j++)
        if(i-a[j]>=0)
            f[i]=f[i]<f[i-a[j]]+1?f[i]:f[i-a[j]]+1; 
}