社区讨论

AC但不知道怎么A的,求助玄关

P3195[HNOI2008] 玩具装箱参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mhjif5th
此快照首次捕获于
2025/11/04 03:05
4 个月前
此快照最后确认于
2025/11/04 03:05
4 个月前
查看原帖
这是一份全wa代码
CPP
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
const ll N=50004;
ll qz[N],l,q[N],t=1,w,n,X[N],dp[N];
long double xl(ll a,ll b){
	return (long double)((long double)(X[b]-X[a])/(long double)(qz[b]-qz[a]));
}
int main(){
	scanf("%lld%lld",&n,&l);
	l++;
	for(ll i=1;i<=n;i++){
		scanf("%lld",&qz[i]);
		qz[i]+=qz[i-1];
		qz[i]++;
	}
	q[++w]=0;
	for(ll i=1;i<=n;i++){
		while(t<w&&xl(q[t],q[t+1])<=2*qz[i])t++;
		dp[i]+=dp[q[t]]+(qz[i]-qz[q[t]]-l)*(qz[i]-qz[q[t]]-l);
		while(t<w&&xl(q[w-1],i)<=xl(q[w-1],q[w]))w--;
		q[++w]=i;
		X[i]=dp[i]+2*l*qz[i]+qz[i]*qz[i];
	}
	printf("%lld",dp[n]);
	return 0;
}
可以看到我有一个预处理用 X 数组,当我把他改成了函数实时处理后值与原来不同:
CPP
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
const ll N=50004;
ll qz[N],l,q[N],t=1,w,n,dp[N];
ll X(ll i){
	return dp[i]+2*l*qz[i]+qz[i]*qz[i];
} 
long double xl(ll a,ll b){
	return (long double)((long double)(X(b)-X(a))/(long double)(qz[b]-qz[a]));
}
int main(){
	scanf("%lld%lld",&n,&l);
	l++;
	for(ll i=1;i<=n;i++){
		scanf("%lld",&qz[i]);
		qz[i]+=qz[i-1];
		qz[i]++;
	}
	q[++w]=0;
	for(ll i=1;i<=n;i++){
		while(t<w&&xl(q[t],q[t+1])<=2*qz[i])t++;
		dp[i]+=dp[q[t]]+(qz[i]-qz[q[t]]-l)*(qz[i]-qz[q[t]]-l);
		while(t<w&&xl(q[w-1],i)<=xl(q[w-1],q[w]))w--;
		q[++w]=i;
	}
	printf("%lld",dp[n]);
	return 0;
}
但是照理说一个玩具的 X 赋值所涉及的数组在遍历到其后玩具是是不会改变的
是我眼瞎还是奇怪机制?

回复

2 条回复,欢迎继续交流。

正在加载回复...