社区讨论
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;
}
可以看到我有一个预处理用
CPPX 数组,当我把他改成了函数实时处理后值与原来不同:#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 条回复,欢迎继续交流。
正在加载回复...