题目链接:Click here~~
题意:
中文题不解释。
解题思路:
有三个变量,我们需要考虑下哪两个看做费用,哪个看做价值。
习惯起见,我们把经验看做价值(因为他是状态转移时会增加的量)。
状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-b[k]]+a[k]). ( i 表示杀敌数, j 表示忍耐度, a 表示增加的经验, b 表示减少的忍耐度)
而且怪物可以杀无限次,故可看做完全背包,正向循环。
最后再从第二维中寻找首先出现经验值大于等于所需经验的。
#include <stdio.h> #include <string.h> #define max(a,b) a > b ? a : b #define N 103 int main() { int Exp,Bear,Kind,Maxn; int a,b,dp[N][N]; //a->Exp,b->Bear while(~scanf("%d%d%d%d",&Exp,&Bear,&Kind,&Maxn)) { int ans = -1; memset(dp,0,sizeof(dp)); for(int k=1;k<=Kind;k++) { scanf("%d%d",&a,&b); for(int i=1;i<=Maxn;i++) for(int j=b;j<=Bear;j++) dp[i][j] = max(dp[i][j],dp[i-1][j-b]+a); } for(int j=0;j<=Bear;j++) for(int i=1;i<=Maxn;i++) if(dp[i][j] >= Exp) { ans = Bear-j; goto end; } end: printf("%d\n",ans); } return 0; }