题解：P12432 [NERC2023] Accumulator Apex

· · 题解

因为我们每次都只能取每行最左侧的元素，我们可以记录列表的前缀和数组 sum。

在一行中，当遍历到第 i 列时满足 sum_i>0，就说明我们如果取走 1 至 i 列的元素，x 的值会增加。但是我们要保证在任意时刻 x 非负，就需要计算出 sum_1,sum_2,...,sum_i 的最小值，如果最小值大于 x，我们就无法使 x 非负。

我们不妨这样想，要想获得 sum_i 的加分，必然要有 sum_1,sum_2,...,sum_i 的最小值的花费，对于每组“加分”，记录它加分和花费的多少，每次优先选择花费少的进行加分。如果 x 的值不小于当前最小的花费，我们就可以更新 x。

注意如果 sum_{i-1}>0，从 sum_i 开始的前缀和应该从头开始计算，否则在计算本组加分的值时，上组加分的值也会被计算。

至于每行中每组加分是否是按照从左到右的顺序被选择，因为每行中靠右的组的花费一定不小于靠左的组的花费，所以不会影响答案。

代码如下，可供参考：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int x,k,l,a,sum[N],mi,cnt;
pair<int,int> p[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>x>>k;
    for(int i=1;i<=k;i++){
        cin>>l;
        mi=2147483647;
        for(int j=1;j<=l;j++){
            cin>>a;
            sum[j]=sum[j-1]+a;
            if(sum[j]>0)p[++cnt]={-mi,sum[j]},sum[j]=0;
            else mi=min(mi,sum[j]);
        }
    }
    sort(p+1,p+cnt+1);
    for(int i=1;i<=cnt;i++){
        int a=p[i].first,b=p[i].second;
        if(x>=a)x+=b;
        else break;
    }
    cout<<x;
    return 0;
}