思路：不能用经验作背包，因为获得的经验可以超过升级的经验。有两个限制条件1.杀怪的总数量。2.拥有的疲劳值。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int dp[110][110];//数量 疲劳值 最大经验 int a[110],b[110];// 获得的经验 减去的疲劳值 int main() { int n,m,k,s; // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); while(~scanf("%d%d%d%d",&n,&m,&k,&s))//需要的经验 剩下的疲劳 怪物种类 最多杀怪数 { for(int i=0;i<k;i++) scanf("%d%d",&a[i],&b[i]); memset(dp,0,sizeof(dp)); int ans; for(int i=0;i<k;i++) { for(int j=1;j<=s;j++) { for(int l=b[i];l<=m;l++)//dp[j][l]表示选j种物品疲劳值为l能获得的最大经验值 { dp[j][l]=max(dp[j][l],dp[j-1][l-b[i]]+a[i]); } } } ans=99999999; for(int j=1;j<=s;j++) for(int l=1;l<=m;l++) if(dp[j][l]>=n) { if(ans>l) { ans=l; } } if(ans==99999999)printf("-1\n"); else printf("%d\n",m-ans); } }