1187. 【动态规划】竞赛总分

题目描述

学生在我们USACO的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们能尽可能的多得分。
现在要进行一次竞赛，总时间T固定，有若干类型可选择的题目，每种类型题目可选入的数量不限，每种类型题目有一个si(解答此题所得的分数)和ti(解答此题所需的时间)，现要选择若干题目，使解这些题的总时间在T以内的前提下，所得的总分最大。  

输入

输入包括竞赛的时间，M(1 <= M <= 10000)和题目类型数目N(1 <= N <= 10000)。
后面的每一行将包括两个整数来描述一种"题型"。第一个整数说明解决这种题目能得的分数(1 <= points <= 10000)，第二整数说明解决这种题目所需的时间(1 <= minutes <= 10000)。

输出

单独的一行，在给定固定时间里得到的最大的分数。

样例输入

300 4
100 60
250 120
120 100
35  20

样例输出

605

思路

动态规划可以分成四部分

        dp1: 状态定义

                dp[i] 表示时间为i的最大的分数

        dp2: 初始化数据

                数组全部初始化为0

        dp3: 求解算法（状态转移方程)

if (i + v1[j].second <= n) 枚举时间, 时间+当前题目的时间 <= 规定的时间（满足条件）
	dp[i + v1[j].second] = max(dp[i + v1[j].second], dp[i] + v1[j].first);

dp[i + v1[j].second] 选择之后的时间所达到的分数
= max(选择之后的时间原来所达到的分数, 没有选择的时候的分数 + 当前题目的分数)

很多dp都是这样子的模式

        dp4: 输出答案

                dp[n] 

Code

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

int n, m;
typedef pair<int, int> Ipair;
vector<Ipair> v1;
void Print(vector<int> dp)
{
	for (auto& it : dp) cout << it << ' ';
	cout << endl;
}
int main() {
	cin >> n >> m;
	v1.resize(m + 1);
	for (int i = 1; i <= m; i++) cin >> v1[i].first >> v1[i].second;
	
	vector<int> dp(n + 1, 0); // dp数组, dp[i] 表示时间为i的最大分数
	
	// dp第二步: 求解
	for (int i = 0; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (i + v1[j].second <= n)
				dp[i + v1[j].second] = max(dp[i + v1[j].second], dp[i] + v1[j].first);
		}
		//Print(dp);
	}
	cout << dp[n];
    return 0;
}