P11769 歌唱练习的题解

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

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

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

CPP

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

表示当前最大的后缀，当时间上限出现变化时才进行统计。

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

完整代码如下：

CPP

#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;
}

P11769 歌唱练习的题解

文章操作

相关推荐

评论

P11769 歌唱练习的题解