大部分牛客都使用优化后的二维化一维数组,此处提供最原始二维存储方案(当然优化后存储空间更低)
#include<iostream>
using namespace std;
int main()
{
int t,m;
cin >> t >> m;
int time[101],value[101];
int dp[1001][1001];
for(int i = 1;i <= m;++i)
cin >> time[i] >> value[i];
for(int i = 0;i <= m;++i){
for(int j = 0;j <= t;++j){
if(i == 0 || j == 0)
dp[i][j] = 0;
else{
if(j < time[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - time[i]] + value[i]);
}
}
}
cout << dp[m][t];
}