USACO 3.1.2 Score Inflation （完全背包）

一、题目大意

题目传送门：USACO 3.1.2 Score Inflation

二、解题思路

这是个典型的完全背包，就是不限定物品数量，求最大价值。

刚开始用贪心写的，居然过了11/12的数据，可怕，最后一组过不了，换成了dp才过了全部数据。我以为根据比重排序就行了，但想想感觉好像有点问题，幸好最后一组数据让我WA掉了，要不然我就被带偏了

动归转移方程：dp[i] = max(dp[i], dp[i-v[j].second]+v[j].first);

三、AC代码

#include <bits/stdc++.h>

#define endl '\n'
using namespace std;
using ll =unsigned long long;

template<typename T=int>
inline T read() {
    T x;
    cin >> x;
    return x;
}

template<typename T=int>
void OO(vector <T> v, string comm="") {
    cerr << comm << " : " << endl;
    for (auto i: v) {
        cerr << i << ' ';
    }
    cerr << endl;
}
typedef pair<int, int> pr;
int main() {
    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int n = read(), k = read();
    vector<pr>v(k);
    for(auto &i: v){
        i.first = read();
        i.second = read();
    }
    vector<int>dp(n+1);
    for(int j = 0; j < k; j++){
        for(int i = v[j].second; i <= n; i++){
            dp[i] = max(dp[i], dp[i-v[j].second]+v[j].first);
        }
    }
    cout << dp[n] << endl;
    return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/97135749