竞赛得分

Description

学生在我们USACO的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们能尽可能的多得分。现在要进行一次竞赛，总时间T固定，有若干类型可选择的题目，每种类型题目可选入的数量不限，每种类型题目有一个si(解答此题所得的分数)和ti(解答此题所需的时间)，现要选择若干题目，使解这些题的总时间在T以内的前提下，所得的总分最大。
输入包括竞赛的时间,M(1 <= M <= 10000)和题目类型数目N(1 <= N <= 10000)。
后面的每一行将包括两个整数来描述一种"题型":
第一个整数说明解决这种题目能得的分数(1 <= points <= 10000),第二整数说明解决这种题目所需的时间(1 <= minutes <= 10000)。

Input

第 1 行: 两个整数：竞赛的时间M和题目类型数目N。 第 2-N+1 行: 两个整数：每种类型题目的分数和耗时。

Output

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

Sample Input

300 4
100 60
250 120
120 100
35 20

Sample Output

605

Hink

Time Limit:10000MS
Memory Limit:65536K

解题思路

其实这道题和上一题完全背包的思路是一样的，只不过是输入数据反了一下。
状态转移方程： f [ j ] = m a x ( f [ j ] , f [ j − p [ i ] ] + w [ i ] ) ; f[j]=max(f[j],f[j-p[i]]+w[i]); f[j]=max(f[j],f[j−p[i]]+w[i]);

#include<iostream>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int n,w[10010],m,p[10010],f[10010];
int main()
{
   
	cin>>n>>m;
	for(int i=1;i<=m;i++) 
	 cin>>w[i]>>p[i];
	for(int i=1;i<=m;i++)
	 for(int j=p[i];j<=n;j++)//当时间为j，处理前i个题目的最大分数
	 {
   
	 	f[j]=max(f[j],f[j-p[i]]+w[i]);//状态转移方程
	 }
	cout<<f[n];
	return 0;
}