P2722 [USACO3.1] 总分 Score Inflation

#include<bits/stdc++.h>
using namespace std;
/*
由于此题数据大 不能二维dp 滚动数组 
1.确定状态 dp[i][j]表示前面i种物品容量为j时能装的最大价值
2.确定答案 dp[n][m]
3.状态转移方程 
不装或装不下 dp[i]=pre[i]
装得下 dp[j]=dp[j-t[i]]+p[i]
4.初始值
dp[0][j]=0; 
*/
int n,m;
int p[10005],t[10005];
int dp[10005];
int pre[10005];
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=0;j<=m;j++){
			dp[j]=pre[j];
			if(j>=t[i]){
				dp[j]=max(dp[j],dp[j-t[i]]+p[i]);
			}
		} 
		for(int j=0;j<=m;j++){
			pre[j]=dp[j];
		}
	}
	cout<<dp[m];
	return 0;
}