//这题典型的二维背包问题，因为题目说了每种怪的数量无限//先开始的时候我想定义一个三维的dp,dp[i][j][k]表示前i种//怪杀死j只剩余耐久点为dp[i][j][k]经验的最大值，然后状态//方程就可以得到为dp[i][j][k] = max (dp[i-1][j][k],dp[i][j-1][k-b[i]]+a[i]);//这和完全背包的方程同出一辙，只是最后的答案我却不太清楚怎么找大，//最后看了一下题解，原来我的想法是对的，但最终的结果只要找到满足条件的最大的j就可以啦//最后还可以用上挑战程序设计这本书上对完全背包的空间节省，少去一维//dp[j][k]表示耐久点为j，还能杀怪的只数k时所得到的经验的最大值//则dp[j][k] = max (dp[j][k],dp[j-b[i]][k-1]+a[i]);#include <algorithm>#include <bitset>#include <cassert>#include <cctype>#include <cfloat>#include <climits>#include <cmath>#include <complex>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>#include <deque>#include <functional>#include <iostream>#include <list>#include <map>#include <numeric>#include <queue>#include <set>#include <stack>#include <vector>#define ceil(a,b) (((a)+(b)-1)/(b))#define endl '\n'#define gcd __gcd#define highBit(x) (1ULL<<(63-__builtin_clzll(x)))#define popCount __builtin_popcountlltypedef long long ll;using namespace std;const int MOD = 1000000007;const long double PI = acos(-1.L);template<class T> inline T lcm(const T& a, const T& b) { return a/gcd(a, b)*b; }template<class T> inline T lowBit(const T& x) { return x&-x; }template<class T> inline T maximize(T& a, const T& b) { return a=a<b?b:a; }template<class T> inline T minimize(T& a, const T& b) { return a=a<b?a:b; }const int maxn = 108;int a[maxn];int b[maxn];int dp[maxn][maxn];int n,m,k,s;void init(){for (int i=1;i<=k;i++)scanf("%d %d",&a[i],&b[i]);memset(dp,0,sizeof(dp));}void print(){for (int i=1;i<=m;i++){for (int j=1;j<=s;j++)printf("%d ",dp[i][j]);puts("");}}void solve(){for (int i=1;i<=k;i++){for (int j=b[i];j<=m;j++)//这重循环是完全背包的，，只能顺过来for (int l=s;l>=1;l–)//这重循环可以顺过来dp[j][l] = max(dp[j][l],dp[j-b[i]][l-1]+a[i]);}int flag = 0;int cnt=0;for (int i=m;i>=0;i–)for (int j=1;j<=s;j++)if (dp[i][j]>=n){flag=1;cnt=i;break;}if (!flag)printf("-1\n");else{printf("%d\n",m-cnt);}//print();}int main() {//freopen("G:\\Code\\1.txt","r",stdin);while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF){init();solve();}return 0;}
绊脚石乃是进身之阶。
