二维背包，dp[i][j]表示忍耐度为i,且还可以杀j个怪时能获得的最大经验值

dp[i][j]=max(dp[i][j],dp[i-r[k]][j-1]+e[k]),r[k]为杀死第k种怪掉的忍耐度，e[k]为第k种怪的经验值

注意方程转移时，我们必须要保证考虑第j个阶段时，我们只放入背包中1个怪，也就是说，必须做01背包，不能做完全背包

一开始先枚举的就，再枚举k,再从小到大枚举i,这样就变成做完全背包了，第k类怪可能在同一阶段被放入多次，如果从大到小枚举i就没问题了

 

以下我只是用了一种状态转移方程(有的牛人用了好几种)：

/* * 2159.cpp * *  Created on: 2013年7月29日 *      Author: Administrator */#include 
    
     using namespace std;int dp[105][105];int n,m,K,s,w[105],r[105],e[105];int main(){	int i , j , k , l;	while(cin>>n>>m>>K>>s){		memset(dp,0,sizeof(dp));		for(i=1;i<=K;++i){			cin>>e[i]>>r[i];		}		for(j=1;j<=s;++j){//s:怪的个数			for(k=1;k<=K;++k){//K:怪的种类数				/**				 * m:所剩的忍耐度				 * r[k]:杀掉第k种怪的所掉的忍耐度				 * e[k]:杀掉第k种怪的所获得的的经验值				 *				 *				 */				for(i=m;i>=r[k];--i){					dp[i][j] = max(dp[i][j],dp[i-r[k]][j-1] + e[k]);				}			}		}		/**		 * 以下循环判断到底要掉多少人啊你读才可以获得所需的经验值		 */		for( i = 0 ; i <= m ; ++i ){			//dp[i][j]:忍耐度为i，还可以杀j个怪的时候所能获得的最大的经验值			if(dp[i][s] >= n){				break;			}		}		int ans;		if(i>m){//如果所需的忍耐度>所剩的忍耐度			ans = -1;		}else{			//m-i。所剩的忍耐度-所需的忍耐度			ans = m - i;		}		cout<
     
      <