采药-题解（C++代码——20行以内解决动态规划解法）

解题思路:

dp[i][j]代表在i时间内可以取j种草药时的最大价值，dp[i][j]只与前一种状态dp[i][j-1]与dp[i-time[cur]][j-1]+value[j]有关，即在i时间内可以取j种草药时的最大价值等于在i-time[cur]时间内可以取j-1种草药时的价值加第j种草药的价值与在i时间内可以取j-1种草药时的价值的最大值，即

dp[i][j]=max(dp[i-time[j-1]][j-1]+value[j-1],dp[i][j-1])

代码:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main(){
    int totalTime,totalNum;
    cin>>totalTime>>totalNum;
    int dp[totalTime+1][totalNum+1],value[totalNum],time[totalNum];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<totalNum;i++) cin>>time[i]>>value[i];
    for(int i=1;i<=totalTime;i++)
        for(int j=1;j<=totalNum;j++){
            dp[i][j]=dp[i][j-1];
            if(i>=time[j-1])
                dp[i][j]=max(dp[i-time[j-1]][j-1]+value[j-1],dp[i][j-1]);
        }
    cout<<dp[totalTime][totalNum];
    return 0;
}