(CF1400B)RPG Protagonist

发表于 分类于 ，

原题链接

思路:

不失一般性地讨论 \(s \leq w\) 的情况 (若 \(s > w\), 则两数交换).

枚举自己拿的剑的数量 \(s_{1}\), 最少 0 个，最多 \(min\{cnt_{s}, \lfloor \frac{p}{s} \rfloor \}\) 个.

自己剩余的空间拿尽量多的斧子 \(w_{1}\), 数量为 \(min\{cnt_{w}, \lfloor \frac{p-s_{1}*s}{w} \rfloor \}\) 个

由于 \(s \leq w\), 所以队友拿尽量多的剑答案更优，数量为 \(s_{2} = min\{cnt_{s}-s_{1}, \lfloor \frac{f}{s} \rfloor \}\) 个

队友的剩余空间拿斧子，数量为 \(w_{2}=min\{cnt_{w}-w_{1}, \lfloor \frac{f-s_{2}*s}{w} \rfloor \}\) 个

总数量为 \(s_1 + w_1 + s_2 + w_2\), 枚举 \(s_1\) 选择最大值即可.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        int p,f,cs,cw,s,w;
        scanf("%d %d %d %d %d %d",&p,&f,&cs,&cw,&s,&w);
        if(s>w) {   //若s>w则交换
            int c = s; s = w; w = c;
            c = cs; cs = cw; cw = c;
        } else if(s==w){
            cs += cw;
            cw = 0;
        }
        int ans(0);
        for(int i(0);i<=cs;++i) {   //枚举s1
            if(i>p/s) {
                break;
            }
            int w1 = min((p-i*s)/w,cw);
            int s2 = min(cs-i,f/s);
            int w2 = min((f-s2*s)/w,cw-w1);
            ans = max(ans,i+w1+s2+w2);
        }
        printf("%d\n",ans);
    }
    return 0;
}