洛谷 P1853 投资的最大效益

题目传送门

解题思路:

额.跑n遍完全背包,好像是的

AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int s,d,n,c[11],w[11],tot,f[2500001],ans;

int main() {
    scanf("%d%d%d",&s,&n,&d);
    for(int i = 1;i <= d; i++)
        scanf("%d%d",&w[i],&c[i]);
    while(n--) {
        memset(f,0,sizeof(f));
        for(int i = 1;i <= d; i++)
            for(int j = w[i];j <= s; j += 1000)//这里加1000就行,因为题目里说了w[i]为1000的倍数 
                f[j] = max(f[j],f[j-w[i]] + c[i]),ans = max(ans,f[j]);
        s = ans + s;
    }
    printf("%d",s);
    return 0;
}