题解：AT_arc128_c [ARC128C] Max Dot

因为从前往后推时前面可能为

0

而后往前推则无需判断，因此从后往前推。最终的序列求得一定是阶梯状的，刚开始有最直接的两种贪心想法（令

val

为填到这个位置还剩多少值）：

从后往前找到最大值，并让这个位置（设为 $i$ ）到最大值（位置为 $pos$ ）的值赋上 $\frac{val}{i-pos+1}$
从后往前记录后缀值，每一次提供的答案为 $\frac{val}{i-pos+1} \times \sum_{j=pos}^{i} a_j$

第一种显然错误，如果前面的特别大而后面的特别小。比如 $7~8~9~1$ 且 $m=4,s=4$ 就会赋为 $0~0~2~2$ 而正确答案应赋为 $1~1~1~1$ 。
第二种看似正确，这种贪心保证了每一次选数的最优值。因为每一次都考虑了整个序列，且后面的选数不影响前几次选的因此局部最优解为全局最优解。

但是显然我们还没考虑最大值上限的问题。我一开始是想如果

\frac{val}{i-pos+1}

超过

m

再调整回去。但是如果每一次

\frac{val}{i-pos+1}

都小于

m

那么我们就会给后面的数浪费了很多权值（数又大又后时）。

注意到我们之前的算法是线性的。为什么不是

n^2

的，因为如果每一次

pos

减的少那么

val

减的必然大，反之亦然。每次填完或者

val=0

了就退出必能保证线性。

又注意到

m

最多出现

n

次，因此我们每次暴力枚举

m

的个数即可，时间复杂度

O(n^2)

。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int n;
double m,s,sum,a[N];
double hz[N];
double res,ans;
double c[N];
void solve(int len){
	if(len<0||sum<=0) return;
	double mx=0,pos=0,mper=0;
	for(int i=len;i>=1;i--){
		double slen=len-i+1,per=sum/slen;
		if(per>=m) continue;
		if((hz[i]-hz[len+1])*per>mx) mx=(hz[i]-hz[len+1])*per,pos=i,mper=per;
	}
	res+=mx;
	sum-=(len-pos+1)*mper;
	solve(pos-1);
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=n;i>=1;i--) hz[i]=hz[i+1]+a[i];
	for(int i=0;i<=n;i++){
		if(m*i>s) break;
		res=hz[n-i+1]*m;
		sum=s-i*1.0*m;
		solve(n-i);
		ans=max(ans,res);
	}
	printf("%.15lf",ans);
	return 0;
}

题解：AT_arc128_c [ARC128C] Max Dot

文章操作

相关推荐

评论

题解：AT_arc128_c [ARC128C] Max Dot