题解：P11769 歌唱练习

· · 题解

题解：P11769 歌唱练习

想了好久，总结一下，力求通俗易懂。

贪心思路

1. 考虑转移方向并构造时间序列

前面的决策肯定会影响后面的选择，因为一定要满足单调不降，如果从前往后构造满足条件，那么如果遇到一个小的就完了。所以考虑从后往前构造最多的练习时间。

很显然，必须满足单调不降，那么从后往前构造一定是取后缀最小值，这样一定能保证从当前点到最后是单调递减的且可以最大化每天的练习时间。

2. 求出最大贡献

秉承着一个原则：正数越多越好，负数越少越好。 很容易想到一个思路，从前往后枚举，如果是正数就取时间的最大值，如果是负数就取与前面的相同的时间达到满足单调不降且负数最少（并不是最少的！等会儿会解释）。写完发现喜提零分。

这是为什么呢？看着挺对的啊？重新考虑我们需要的，正数越多越好，负数越少越好这个原则一定是对的，那么说明我们的思路并不能保证负数最少。

举个例子，下方第一行是构造出的时间序列，第二行是 w_i。

1  2  3     4  5
1  2  -100  4  5

在这个例子中，很明显最优的方案是前面三天都不练习，时间为 0，这是最优的方案。

举出了反例，那么重新构造思路，不能构造出负数最小，那么就构造出正数最大，考虑样例与刚才举的例子。

:::info[解释样例] 为什么样例取了负数？因为这个负数与后面的可以组成一段非负的贡献。 ::: :::info[解释上面的例子] 为什么不取这个负数？因为这个负数与后面的不能组成一段非负贡献的区间。 :::

这样就可以构造出最终的思路，从后往前构造，每次找到最短且连续的非负贡献区间，把原来的序列分成若干个贡献非负的区间，时间就取当中最小的，如果最后的一个区间的贡献仍未负数，那么干脆舍弃。

代码

比较简单，代码就不加注释了（别忘记开长整型）。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int t[1000010];
int w[1000010];
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&t[i]);
    for(int i=1;i<=n;i++){
        scanf("%lld",&w[i]);
        w[i]+=w[i-1];
    }
    for(int i=n-1;i>=1;i--){
        t[i]=min(t[i],t[i+1]);
    }
    int last=n;
    int ans=0;
    for(int i=n;i>=1;i--){
        if(w[last]-w[i-1]>=0){
            ans+=t[i]*(w[last]-w[i-1]);
            last=i-1;
        }
    }
    printf("%lld",ans);
    return 0;
}