关于这个题的精度问题

我没有发现长度

>1

的段是很少的，我想的办法是将斜率优化与高精度分开——先用 longdouble DP 出决策点，再用高精度计算答案。

我的精度死活过不了。事实上我调整了一下，用

p=30

跑出来的决策点与用

p=100

跑出来的决策点截然不同。

本来我认命了，但是开题解发现这样做的题解还不少，但是我研究了一个小时也没看出来为什么他们的精度不会有问题而我的会爆。

我在 LOJ 上提交了

p=300

的代码，是没有问题的，所以我斜率优化部分是无误的。

并且我在本地测试了题解在第 20 个点的表现，结果确实没有任何精度问题。

但是几篇题解的作者看上去很久不上洛谷了。有没有用斜率优化与高精度分开的老哥通过了此题，可以说说是为什么吗？

我的代码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=8010;
long long a[N];
double f[N],g[N];
short pre[N][N]; 
int q[N],l,r;
vector<int> vt;
void print(int k,int n)
{
	vt.push_back(n);
	if(!k) return ;
	print(k-1,pre[k][n]);
}
signed main()
{
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,k,p;
    cin>>n>>k>>p;
    for(int i=1;i<=n;i++) cin>>a[i];
	Decimal ans=a[1];
    for(int i=0;i<=n;i++) f[i]=a[1];
    for(int i=1;i<n;i++) a[i]=a[i+1];
    n--,sort(a+1,a+1+n),k=min(k,n);
    for(int i=1;i<=n;i++) a[i]+=a[i-1];
	int now=1;
    for(int i=1;i<=k;i++)
    {
        l=1,r=0,q[++r]=0;
        for(int j=0;j<=n;j++) g[j]=f[j],f[j]=0;
        auto work=[&](int x,int y){return ((a[y]-g[y])-(a[x]-g[x]))/(y-x);};
        auto work2=[&](int x,int y){return (g[x]+a[y]-a[x])/(y-x+1);};
        for(int j=1;j<=n;j++)
        {
            while(l+1<=r&&work(q[r-1],q[r])>=work(q[r],j)) r--;
            q[++r]=j;
            while(l+1<=r&&work2(q[l],j)<=work2(q[l+1],j)) l++;
            f[j]=work2(q[l],j);
			pre[i][j]=q[l];
        }
		if(pre[i][n]==n) break;
		now=i;
    }
	print(now,n);
	sort(vt.begin(),vt.end());
	vt.erase(unique(vt.begin(),vt.end()),vt.end());
	for(int i=0;i+1<vt.size();i++)
	{
		ans+=a[vt[i+1]]-a[vt[i]];
		ans/=vt[i+1]-vt[i]+1;
	}
	cout<<ans.to_string(1.2*p);
    return 0;
}

题解代码：

CPP

using namespace std;
#define RI register int
typedef long double db;
typedef long long LL;
const int N=8005;
Decimal ans;
int orzyyb,n,K,P,kpos;db kans;
int h[N],qid[N];LL s[N];short las[N][N];db f[2][N];
struct point{db x,y;}que[N];
point operator - (point A,point B) {return (point){A.x-B.x,A.y-B.y};}
db operator * (point A,point B) {return A.x*B.y-B.x*A.y;}

Decimal getans(int x,int y) {
	if(x==0) return 0;
	return (getans(x-1,las[x][y])+s[y]-s[las[x][y]])/(y-las[x][y]+1);
}

int main() {
	freopen("1.in","r",stdin);
	freopen("2.out","w",stdout);
	scanf("%d%d%d",&orzyyb,&K,&P);
	scanf("%d",&h[0]);
	for(RI i=1;i<orzyyb;++i) {
		int x;scanf("%d",&x);
		if(x>h[0]) h[++n]=x-h[0];
	}
	sort(h+1,h+1+n);
	for(RI i=1;i<=n;++i) s[i]=s[i-1]+h[i];
	if(K>n) K=n;
	for(RI i=1,t=1;i<=K;++i,t^=1) {
		int he=1,ta=1;
		que[1]=(point){(db)i-2,(db)s[i-1]-f[t^1][i-1]},qid[1]=i-1;
		for(RI j=i;j<=n;++j) {
			point P=(point){(db)j,(db)s[j]};
			while(he<ta&&(P-que[he+1])*(P-que[he])<0) ++he;
			las[i][j]=qid[he],f[t][j]=(db)(P.y-que[he].y)/(db)(P.x-que[he].x);
            cout<<qid[he]<<' '<<f[t][j]<<'\n';
			P=(point){(db)j-1,(db)s[j]-f[t^1][j]};
			while(he<ta&&(que[ta]-que[ta-1])*(P-que[ta-1])<0) --ta;
			++ta,que[ta]=P,qid[ta]=j;
		}
        cout<<'\n';
        if(i>10) exit(0);
		if(f[t][n]>=kans) kans=f[t][n],kpos=i;
	}
	ans=getans(kpos,n)+h[0];
	cout<<ans.to_string(P<<1)<<endl;
	return 0;
}

关于这个题的精度问题

讨论操作

回复

相关推荐

关于这个题的精度问题