采药 dp

题目

#include<bits/stdc++.h>
using namespace std;
int tim[1001] = {0};
int w[1001] = {0};
int dp[101][1001]={0};//dp[i][j]表示到第i课草药在限制条件为所j取得得最大价值
//状态转移方程：
//dp[i][j] = max(dp[) 
int main()
{
	int t,m;
	cin>>t>>m;
	
	for(int i=1;i<=m;i++)
	{
		cin>>tim[i]>>w[i];
	}
	
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=t;j++)//表示时间 
		{
			//状态转移方程，分两种情况 
			if(j<tim[i]) dp[i][j] = dp[i-1][j];//第i棵草药不采 
			else if(j>=tim[i]) dp[i][j] = max(dp[i-1][j-tim[i]]+w[i],dp[i-1][j]);
		} 
	}
	cout<<dp[m][t]<<endl;
	return 0;
}