/ Vijos / 题库 / 采药 /

题解

301 条题解

  • -2
    @ 2017-07-08 19:48:25
    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    
    
    using namespace std;
    
    int main(){
        int t, m;
        cin >> t >> m;
        int time[m + 1];
        int value[m + 1];
        for (int i = 1; i <= m; i++){
            cin >> time[i] >> value[i];
        }
        
        int dp[m + 1][t + 1];
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= m; i++){
            for (int j = 0; j <= t; j++){
                if (j - time[i] >= 0) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - time[i]] + value[i]);
                else dp[i][j] = dp[i - 1][j];
            }
        }
        
        cout << dp[m][t] << endl;
        return 0;
    }
    

信息

ID
1104
难度
4
分类
动态规划 | 背包 点击显示
标签
递交数
16819
已通过
6525
通过率
39%
被复制
37
上传者