Sad Robin阅读理解.txt

Petlyaaaaa · 2024-04-03 17:56:06 · 个人记录

题目背景：

可以跳

题目描述：

用几包火药做子弹，限制最高膛压。

“不能打开一包不用完”说明火药以包装为单位，不能真按粉末乱用。

“同时尽可能把我那点以质量为单位买的超小包装火药用完”，本题唯一难度（其实我不这么觉得），首先对该句再次进行简化拆分

“以质量为单位”买的“包装火药”“用完”（这条上面写了

“以质量为单位”“火药”“用完”

“质量为单位”“火药”“用完”

易得

简化题面

一些故意设置的坑：

1. 题目背景全部

2. 单位膛压

3. 两个“用完”连用

4. 提醒你输出的是“x包”

5. 彩蛋/提示全部

代码

#include <bits/stdc++.h>
#define Robin SKK//谁是罗宾？
using namespace std;
int t, P, N;
int p[1001], m[1001];
int dp[100001][2];//增开一维数组存火药包数
int main() {
    scanf("%d", &t);
    for (int l = 1; l <= t; l++) {
        for (int i = 0; i < 100001; i++) { //为多测准备的初始化
            for (int j = 0; j < 2; j++) {
                dp[i][j] = 0;
            }
        }
        scanf("%d%d", &P, &N);
        for (int i = 1; i <= N; i++)
            scanf("%d%d", &p[i], &m[i]);
        for (int i = 1; i <= N; i++)
            for (int j = P; j >= p[i]; j--) {//01背包样板代码，用了滚动数组优化那种
                if (dp[j][0] < dp[j - p[i]][0] + m[i]) {//比较当前最大质量与上一层质量+加入的质量的大小
                    dp[j][0] = dp[j - p[i]][0] + m[i];//若有更大的值则更新最大质量
                    dp[j][1] = dp[j - p[i]][1] + 1;//已判断确认最优方案，在最优方案情况下包数+1
                }
            }
        printf("%d\n", dp[P][1]);
    }
    return 0;
}