解题思路:
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语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:535 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:511 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:619 |
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:561 |
2^k进制数 (C语言描述,蓝桥杯)浏览:1420 |
C语言程序设计教程(第三版)课后习题11.8 (C语言代码)浏览:683 |
简单的a+b (C语言代码)浏览:629 |
敲七 (C语言代码)浏览:2700 |
简单的a+b (C语言代码)浏览:434 |
拆分位数 (C语言代码)浏览:441 |