题意 : 中文题不详述。
思路 : 二维背包,dp[i][h]表示当前忍耐值为i的情况下,杀了h个怪得到的最大经验值,状态转移方程:
dp[i][h] = max(dp[i][h],dp[i-a[j].toler][h-1]+a[j].exper) ;
//
#include <stdio.h>
#include <string.h>
#include <iostream> using namespace std ; struct node
{
int exper ;
int toler ;
}a[] ; int dp[][] ; int main()
{
int n,m,k,s ;
while(~scanf("%d %d %d %d",&n,&m,&k,&s))
{
for(int i = ; i <= k ; i++)
scanf("%d %d",&a[i].exper,&a[i].toler) ;
memset(dp,,sizeof(dp)) ;
int ans = - ;
for(int i = ; i <= m ; i++)//当前忍耐度下得到的最多经验
{
for(int j = ; j <= k ; j++)
{
for(int h = ; h <= s ; h++)
if(i >= a[j].toler)
dp[i][h] = max(dp[i][h],dp[i-a[j].toler][h-]+a[j].exper) ;
}
if(dp[i][s] >= n)
{
ans = m-i ;
break;
}
}
printf("%d\n",ans) ;
}
return ;
}