题解 | #采药#

大部分牛客都使用优化后的二维化一维数组，此处提供最原始二维存储方案（当然优化后存储空间更低）

#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];
}