notes：题目还没有放在题库里 所有链接都是比赛里的

魔法咒语（完全背包）

思路

这道题其实就是一道完全背包模板，状态为 $f[i]$ 是伤害为 $i$ 时消耗的魔法点数的最小值，但是这道题的 $f[0]=0$ 代表伤害为 $0$ 时需要 $0$ 点法力值。并且最大值枚举到 $100000$ ，而且最开始时要将 $f[i]$ 赋值成最大值（因为答案要最小值），最后从 $h$ 往上枚举最小值。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=1e5+10;
int f[tt];

signed main(){
	freopen("mana.in","r",stdin);
	freopen("mana.out","w",stdout);
	int h,n;
    cin >>h>>n;
    memset(f,0x3f,sizeof f);
    f[0]=0;
    for(int i=1;i<=n;i++){
    	int x,y;
    	cin >>x>>y;
    	for(int j=x;j<=100000;j++){
    		f[j]=min(f[j],f[j-x]+y);
		}
	}
	int ans=2e9;
	for(int i=h;i<=100000;i++){
		ans=min(ans,f[i]);
	}
	cout <<ans;
    return 0;
}

自助餐（01背包）

思路

先按照消耗时间排序（ 从小到大 ），这样可以枚举到每一种方案。接下来就是 $01$ 背包 的模板。最后，把所有的状态枚举一遍，求最大值输出就好了。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=6e3+10,op=3e3+10;
int dp[tt];
int ans=-1;
int n,t;

struct node{
    int a,b;
}f[op];

bool cmp(node x,node y){
    return x.a<y.a;
}

signed main(){
    freopen("free.in","r",stdin);
    freopen("free.out","w",stdout);
    cin >>n>>t;
    for(int i=1;i<=n;i++){
        cin >>f[i].a>>f[i].b;
    }
    sort(f+1,f+1+n,cmp);
    for(int i=1;i<=n;i++){
        for(int j=t+f[i].a-1;j>=f[i].a;j--){
            dp[j]=max(dp[j],dp[j-f[i].a]+f[i].b);
        }
    }
    for(int i=1;i<=6e3;i++){
        ans=max(ans,dp[i]);
    }
    cout <<ans;
    return 0;
}

谢谢