解题思路:
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语言代码)浏览:3908 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:563 |
C语言训练-计算1~N之间所有奇数之和 (C语言代码)浏览:721 |
C语言程序设计教程(第三版)课后习题9.4 (C语言代码)浏览:735 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:620 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:629 |
打水问题 (C语言代码)浏览:1072 |
用筛法求之N内的素数。 (C语言代码)浏览:1261 |
字符串的输入输出处理 (C语言代码)浏览:945 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:1258 |