采药 （C++代码）(DP动态规划、01背包)

解题思路:

注意事项:

参考代码:

#include<stdio.h>
#include<algorithm>
int main()
{
     int T,M;
     scanf("%d %d",&T,&M);
     int requiredTime[M+1];
     int drugValue[M+1];
     int dp[M+1][T+1];
     for(int i=1;i<=M;++i)
     {
       scanf("%d %d",&requiredTime[i],&drugValue[i]);
     }
     for(int i=0;i<=M;++i)dp[i][0]=0;
     for(int i=0;i<=T;++i)dp[0][i]=0;
     for(int i=1;i<=M;++i)
     {
      for(int j=1;j<=T;++j)
      {
           if(j<requiredTime[i])
                dp[i][j]=dp[i-1][j];
           else
                dp[i][j]=std::max(dp[i-1][j],dp[i-1][j-requiredTime[i]]+drugValue[i]);
      }
     }
     printf("%d\n",dp[M][T]);
        return 0;
}