P11769 歌唱练习 的题解

· · 题解

我能独立想出来这道题真是个奇迹！

每天练习的时间是单调不降的，等于我今天练了多久时间，以后每天都只至少要练这么久的歌。所以我当时先想到说需要对收益后缀和一下。

过了会儿我又想到说是单调不降的，所以就顺手处理一下时间的数组。这两段话合起来就是这段代码：

for(int i=n-1;i>=1;i--)t[i]=min(t[i],t[i+1]);
for(int i=n;i>=1;i--)sum[i]=sum[i+1]+w[i];

额然后我就停止运行了好久。

额好吧还是回到时间单调不降这件事上。所以打算效仿前面，倒序统计答案。然后很快就想到说我可以把这 n 天分成几段，每一段的时间上限都是不同的，时间上限不同就断开成两段。从后往前统计时使用一个变量 p 表示当前最大的后缀，当时间上限出现变化时才进行统计。

额好吧我觉得还是讲得有点模糊，但是尽力了。

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f;
}
inline void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9){write(x/10);}
    putchar((x%10)+48);
}
const int N=1e6+7;
int n,t[N],w[N],sum[N],ans,p;
signed main(){
    n=read();
    for(int i=1;i<=n;i++)t[i]=read();
    for(int i=1;i<=n;i++)w[i]=read();

    for(int i=n-1;i>=1;i--)t[i]=min(t[i],t[i+1]);
    for(int i=n;i>=1;i--)sum[i]=sum[i+1]+w[i];

    p=sum[n];
    for(int i=n;i>=1;i--){
        if(t[i]!=t[i-1]){
            if(p>0)ans+=p*(t[i]-t[i-1]);
        }
            p=max(sum[i-1],p);

    }
    //if(p>0)ans+=p*t[1];
    write(ans);
    return 0;
}