解题思路:
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; }
0.0分
7 人评分
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:694 |
wu-淘淘的名单 (C++代码)浏览:1331 |
sizeof的大作用 (C语言代码)浏览:1024 |
Hello, world! (C语言代码)浏览:821 |
简单的a+b (C语言代码)浏览:818 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:455 |
C语言程序设计教程(第三版)课后习题8.7 (C语言代码)浏览:795 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:553 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:602 |
字符删除 (C语言代码)浏览:715 |