1856: 解题数量

题目描述
编程竞赛网站提供了比赛题目。比赛有D个难度等级，每个难度等级的每个题目都根据其难度分配一个分数，每个难度等级都有p个题目。目前，对于1到D（含）之间的每个整数i，都存在分数为100*i分的pi问题，即第1级难度对应的每个题目分数是100*1，第2级难度对应的每个题目分数是100*2，第D级难度对应的每个题目分数100*D。这些p1+…+pD问题是编程竞赛网站上可用的所有问题。
每一个参赛的用户都有一个总分来记录所做的题目。用户的总得分是以下两个方面组成：
基本分数：用户解决的所有问题的分数之和。
完成奖励：当用户解决完该等级所有问题之后，除了基础分数，还有奖励分数c 。

作为比赛的一个新用户，现在没有解决任何问题。给自己定下一个目标是总分达到G或以上。为了实现这个目标，至少需要解决多少题目？

输入
输入D+1行
第一行输入两个整数：D G
从第二行开始输入D行，每行两个整数：p c
输入格式如下：
D G
p1  c1
:
pD  cD

条件：
1≤D≤10
1≤pi≤100
100≤ci≤106
100≤G
ci和G都是100的倍数
总分可以是G或者更高

输出
输出需要解决的题目的最小数量，使得总分达到G或以上。注意，目标总是可以实现的。
样例输入 Copy
2 700
3 500
5 800
样例输出 Copy
3

提示
样例1说明：
在样例1中有3道100分的题，6道200分的题。全部解决了3道100分的题，奖励500分；全部解决了5道200分的题，奖励800分。目标总分是700分或者往上。
按照贪心的解决方案，先解决分数大的题目，这样之间做4道200分的题，得到800分，就可以。但是，如果解决了3道100分的题目，然后奖励500分，这样也能得到800分，这样可以用更少的题来实现目标。
样例输入2：
2 2000
3 500
5 800
样例输出2：
7
样例2说明：
可以这样实现目标，先做5道200分的题，获得800分的奖励，再2道100分的题，做7道题就实现目标。
样例输入3：
2 400
3 500
5 800
样例输出3：
2
样例3说明：
直接做2道200分的题
样例输入4：
5 25000
20 1000
40 1000
50 1000
30 1000
1 1000
样例输出4：
66

来源/分类
二进制枚举 贪心

救命，很急

首先明确一个结论，一定存在这样的最优解满足：如果100*i分的题目没有做完，那么所有小于j<i的100*j分的题目，要么全做要么一题都不做。

因为i类题目的得分比j类题目高，在i类题目没做完的情况下去做j类题目一定是为了拿奖励分数，所以j类题目要么不做要么做光。

所以只需要枚举 2^D种每类题目做或不做的情况，再在其上枚举一种做了但没做完的贪心算出题目数，其他分数做了就是全做，然后记录满足条件的最小做题数就行了。

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    Solution(int D, int G, const vector<int>& p, const vector<int>& c)
    : D(D), G(G), p(p), c(c) {

    }

    // depth搜索深度
    void dfs(int depth) {
        if(depth == D) {
            if(sum < G) return; // 把选择的类型做完也不足以达成分数G，无需继续计算

            // 枚举一个类型做了但没全做
            for(int ii=0;ii<x.size();ii++) {
                int i = x[ii];
                int presum = sum - 100*(i+1)*p[i]-c[i]; // 算出除i类型外所有做了的所有题目的分数
                int precnt = cnt - p[i]; // 算出除i类型外做了的所有题目的数量
                if(presum >= G) continue; // 如果出去i类型已经超分则肯定可以完全不做i类型的题目，会在另外的情况枚举到，这里直接忽略
                if(precnt >= result) continue; // 如果不做i类型已经比当前最优解更差，那一定无法形成最优解，忽略
                int t = precnt + min((G - presum) / (100*(i+1)), p[i]); // 除i类型外的做题数 + 贪心得到i类型需要做的题数
                result = min(result, t);
            }
        } else {
            dfs(depth+1); // 不做第depth类题

            x.push_back(depth);
            sum += 100*(depth+1)*p[depth]+c[depth];
            cnt += p[depth];
            dfs(depth+1); // 做第depth类题
            cnt -= p[depth];
            sum -= 100*(depth+1)*p[depth]+c[depth];
            x.pop_back();
        }

    }

    int solve() {
        dfs(0);
        return result;
    }

private:
    int D;
    int G;
    vector<int> p;
    vector<int> c;

    vector<int> x;
    int sum = 0; // 当前做的题目的最大得分
    int cnt = 0; // 当前做的题目类型的题目数的和

    int result = 1e9;
};

int main() {
    Solution s1(2, 700, {3, 5}, {500, 800});
    cout << s1.solve() << endl;

    Solution s2(2, 2000, {3, 5}, {500, 800});
    cout << s2.solve() << endl;

    Solution s3(2, 400, {3, 5}, {500, 800});
    cout << s3.solve() << endl;

    Solution s4(5, 25000, {20, 40, 50, 30, 1}, {1000, 1000, 1000, 1000, 1000});
    cout << s4.solve() << endl;
    
    return 0; 
}

我先前觉得还可以推出：如果100*i分的题目没有做完，那么对于所有k>i的100*k分的题目，全都没做。实际上不能推出此结论，对于k>i的100*k分题目也可能是全做完的

[此贴子已经被作者于2023-1-17 17:29编辑过]