一道大水题完全背包模板题

rt，因为每种题目的数量不限，所以这道题使用完全背包dp。 那么这道题其实跟着五步走就行

1. 划分阶段：我们以题目的种类和总耗时来划分
2. 确定状态变量$dp[i]$表示在$i$时间段的最高得分
3. 确定状态转移方程：对于每个$dp[j]$都能通过$dp[j-t[i]]$推出($t[i]$表示第$i$种题目的耗时)，所以我们可以推出状态转移方程为dp[j]=max(dp[j],dp[j-t[i]]+p[i]
4. 设定边界，因为要进行最大值比较，所以设$dp[0]$~$dp[n]$为0，但是如果声明的是全局数组，那么数组会自动将所有变量初始化为0
5. ACCODE：

#include<iostream>
using namespace std;
int m,n,p[10001],t[10001],dp[10001];//三个数组分别表示每个种类的分值，每个种类的耗时，和在耗时i最多能拿多少分
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>p[i]>>t[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=t[i];j<=m;j++)//从t[i]开始，防止越界，到总时间m结束
		{
			dp[j]=max(dp[j],dp[j-t[i]]+p[i]);//比较当前和从前面推来这两个分值的大小
		}
	}
	cout<<dp[m];
}