dp[i][j]记录疲劳度用了i，杀了j个怪所获得的最大经验。
View Code
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int dp[103][103]; int w[103],p[103]; int main() { int n, m, k, s, i, j, x; while(~scanf("%d%d%d%d",&n,&m,&k,&s)) { for(i=1;i<=k;i++) scanf("%d%d",&p[i],&w[i]); memset(dp,0,sizeof(dp)); for(i=1;i<=m;i++) { for(j=1;j<=s;j++) for(x=1;x<=k;x++) if(i>=w[x])dp[i][j]=max(dp[i][j],dp[i-w[x]][j-1]+p[x]); if(dp[i][s]>=n)break;//经验够了就可以停了 } printf("%d\n",m-i); } return 0; }