2020牛客多校第八场 K. Kabaleo Lite(整体和拆分考虑)

题意: n n n种菜,每种菜利润为 a i a_i ai,数量为 b i b_i bi,问在尽可能服务多的客人的情况下,可以获得的最大利润是多少(可以为负数)。注意:除了吃第一种菜,吃第 x x x种菜前必须先吃第 x − 1 x-1 x1种菜 ( x ≥ 2 ) (x\geq 2 ) (x2)。总共有 T T T组数据。
数据范围: 1 ≤ T ≤ 10 , 1 ≤ n ≤ 1 0 5 , − 1 0 9 ≤ a i ≤ 1 0 9 , 1 ≤ b i ≤ 1 0 5 1\leq T\leq 10, 1\leq n\leq 10^5, -10^9\leq a_i\leq 10^9, 1\leq b_i\leq 10^5 1T10,1n105,109ai109,1bi105

题解:
最多客人数即 b 1 b_1 b1

第一种:整体考虑。
由于第一种菜必选,故从第二种菜开始考虑每次贪心地选可以吃到的总利润最大的菜 x x x,且 x x x的前置所有菜都没有被其他先来的客人吃完。则吃完后可以区间修改 b [ 1 , x ] b[1,x] b[1,x]都减 1 1 1

第二种:拆分考虑。
考虑到第 x x x种菜的利润是否大于前面吃到的最大利润,如果大于,则把 x x x这个菜全部吃掉(最多吃 m i n i ∈ [ 1 , x ] { b i } \underset{i\in[1,x]}{min}\{b_i\} i[1,x]min{bi}盘),否则继续往后考虑直到利润大于前面吃到的最大利润。

拆分考虑的代码:

#includebits/stdc++.h
using namespace std;
 
typedef long long ll;
 
templatetypename T
inline T Read(){
    T s = 0, f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch)) {s = (s  3) + (s  1) + ch - '0'; ch = getchar();}
    return s * f;
}
 
inline void print(__int128 x){
    if(x  0){
        putchar('-');
        x = -x;
    }
    if(x  9) print(x / 10);
    putchar(x % 10 + '0');
}
 
#define read() Readint()
#define readl() Readll()
 
const int N = 1e5 + 10;
const int M = N  1;
ll a[N], b[N];
int n;
 
inline void prints(__int128 x){
    if(x  0){
        putchar('-');
        x = -x;
    }
    if(x  9) prints(x / 10);
    putchar(x % 10 + '0');
}
 
void solve(int num) {
    n = read();
    for(int i = 1; i = n; i++) a[i] = readl(), a[i] += a[i - 1];
    for(int i = 1; i = n; i++) b[i] = readl();
    for(int i = 2; i = n; i++) b[i] = min(b[i - 1], b[i]);
     
    __int128 ans = (__int128)a[1] * b[1];
    int l = 1, r = 2;
     
    while(r = n) {
        while(r = n  a[r] = a[l]) ++r;
        if(r == n + 1) break;
        ans += (__int128)(b[r]) * (a[r] - a[l]);
        l = r;
    }
     
    printf("Case #%d: %lld ", num, b[1]);
    prints(ans);
    puts("");
 
}
 
int main()
{
    int T = 1;
    T = read();
    for(int i = 1; i = T; ++i) {   
        solve(i);
    }
}
最新回复(0)
/jishup1Xcnr1eYAnSVv6mFrAH70fk9CgUt2pzwrK_2FeT_2Fg0Ms_3D4794963
8 简首页