Krypton DP,01背包 （2020 China Collegiate Programming Contest Changchun Onsite）

原题链接

题意

有n元钱去买东西
东西都是固定的
第一列是买这个需要的花费
第二列是买这个可以获得几个东西
第三列是第一次买这个东西时可以免费获赠的东西
（差不多是首充概念）

问有n元钱，最多可以买到几个物品？

思路

通过观察发现，除了第一次购买，其他都是第一次买10个物品，那么我们可以转换思路为，N元钱如何才能获得更多的奖励，用01背包即可，因为一元钱都可以买到10个物品，在此基础上，我们使奖励多就行了，跑01背包即可。体积为总钱数，价值为首充可额外获得的钱数。$$f[i][j]=max(f[i][j],f[i?1][j?v[i]]+w[i])$$

最后的答案是$n?10+f[7][n]$

代码

#include<bits/stdc++.h>
using namespace std;
int m;
int w[10] = {
    0, 8, 18, 28, 58, 128, 198, 388};
int v[10] = {
    0, 1, 6, 28, 88, 198, 328, 648};
int f[20][20000];
int main()
{
    cin >> m;for (int i = 1; i <= 7; i ++ ){
    for (int j = 1; j <= m; j ++ ){
    if (j >= v[i]){
    f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);}else{
    f[i][j] = f[i - 1][j];}}}cout << m * 10 + f[7][m] << endl;return 0;
}

总结

康复训练。。。