题解 | #考试策略#

当成特殊的背包问题，用动态规划的方法。 核心：dp[x]表示在考试时间剩下x分钟时，能获得的最高分数。 两层循环，外层遍历物品(即本题中的考试题目，完整做完一题和部分做题视为同一个物品的两种价格和价值)，内层循环遍历剩余时间。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int p[n+1],a[n+1],q[n+1],b[n+1];
    int total=120;
    p[0]=a[0]=q[0]=b[0]=0;
    for(int i=1;i<=n;i++){
        int temp,tema,temq,temb;
        cin>>temp>>tema>>temq>>temb;
        p[i]=temp;
        a[i]=tema;
        q[i]=temq;
        b[i]=temb;
    }
    vector<int> dp(total+1, 0); //dp[x]指在不超过x元的情况下最多能花多少钱
    for(int i = 1; i <= n; i++) //顺序遍历物品
    {
        for(int j = total; j >= 1; j--) //倒序遍历背包容量
        {
            if(j >= p[i])
            {
                dp[j] = max(dp[j], dp[j - p[i]] + a[i]);
            }
            if(j>=q[i])
            {
                dp[j] = max(dp[j], dp[j - q[i]] + b[i]);
            }
        }
            
    }
    cout << dp[total] << endl;
    return 0;
}