小明同学在参加一场考试,考试时间2个小时。试卷上一共有n道题目,小明要在规定时间内,完成一定数量的题目。 考试中不限制试题作答顺序,对于 i 第道题目,小明有三种不同的策略可以选择: (1)直接跳过这道题目,不花费时间,本题得0分。
(2)只做一部分题目,花费pi分钟的时间,本题可以得到ai分。 (3)做完整个题目,花费qi分钟的时间,本题可以得到bi分。
小明想知道,他最多能得到多少分。
输入描述:
第一行输入一个n数表示题目的数量。 接下来n行,每行四个数p_i,a_i,q_i,b_i。(1≤n≤100,1≤p_i≤q_i≤120,0≤a_i≤b_i≤1000 )。
输出描述:
输出一个数,小明的最高得分。
输入例子1:
4 20 20 100 60 50 30 80 55 100 60 110 88 5 3 10 6
输出例子1:
94
#include<iostream>
#include<vector>
using namespace std;
int MAX(const int a,const int b,const int c){
if(a > b && a > c){
return a;
}
else if(b > a && b > c){
return b;
}
else{
return c;
}
}
int main(){
int n;
scanf("%d",&n);
vector<vector<int>> Vec(n,vector<int>(4));
vector<vector<int>> dp(n + 1,vector<int>(121,0));
for(int i = 0;i < n;i ++){
for(int j = 0;j < 4;j ++){
scanf("%d",&Vec[i][j]);
}
}
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= 120;j ++){
if(Vec[i - 1][0] > j){
dp[i][j] = dp[i - 1][j];
}
else if(Vec[i - 1][0] <= j && j < Vec[i - 1][2]){
dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - Vec[i - 1][0]] + Vec[i - 1][1]);
}
else{
dp[i][j] = MAX(dp[i - 1][j],dp[i - 1][j - Vec[i - 1][0]] + Vec[i - 1][1],dp[i - 1][j - Vec[i - 1][2]] + Vec[i - 1][3]);
}
}
}
int Result = dp[n][120];
printf("%d\n",Result);
return 0;
}
标签:小明,背包,题目,--,int,DP,return,dp,Vec From: https://blog.51cto.com/u_13121994/5798380