## 【BZOJ 4518】[Sdoi2016] 征途

#include<bits/stdc++.h>
#define pow(x) ((x)*(x))
#define LL long long
using namespace std;

const int N = 3000+9;
const LL INF = 1e16;

LL f[N][N];
short n,m,l[N],sum,que[N][N],t1[N],t2[N];
double slope[N][N],Y[N][N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int main(){
for (int i=1;i<=n;i++) sum += (l[i] = read()), l[i] += l[i-1];
for (int i=0;i<m;i++) t1[i] = 1, f[n][i] = -1; t2[0] = 1;
for (int i=1;i<=n;i++) for (int j=m-1;~j;j--) {
if (t1[j]>t2[j]) continue; double tmp = 2.0*m*((double)m*l[i]-sum);
while (t2[j] > t1[j] && slope[j][t1[j]] <= tmp) t1[j]++;
f[i][j+1] = f[que[j][t1[j]]][j] + pow(sum-(LL)m*(l[i]-l[que[j][t1[j]]]));
tmp = f[i][j+1] + pow((double)m*l[i]);
while (t1[j+1] < t2[j+1] && ((tmp-Y[j+1][t2[j+1]])/(l[i]-l[que[j+1][t2[j+1]]]) <= slope[j+1][t2[j+1]-1])) t2[j+1]--;
if (t1[j+1] <= t2[j+1]) slope[j+1][t2[j+1]] = (tmp-Y[j+1][t2[j+1]])/(l[i]-l[que[j+1][t2[j+1]]]);
t2[j+1]++; que[j+1][t2[j+1]] = i; Y[j+1][t2[j+1]] = tmp;
} LL vout = INF;
for (int i=1;i<=m;i++) if (~f[n][i]) vout = min(vout,f[n][i]+(LL)(m-i)*pow(sum));
printf("%lld\n",vout/m); return 0;
}


## 【NOI六连测】[D4T1] 数学

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const int MAXN = 200000+9;
const int K = 50+9;

double x[K][MAXN/2],y[K][MAXN/2],rev[MAXN],ret,arr[MAXN];
int AA[MAXN],n,k,l[K],r[K],pos[K][MAXN/2];

char c=getchar(); int buf=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
return buf*f;
}

#define slope(t,b,a) (y[t][a]-y[t][b])/(x[t][a]-x[t][b])

inline void update(int t, double X, double Y, int i){
int tmp = r[t]+1; x[t][tmp]=X; y[t][tmp]=Y;
while (l[t] < r[t]) if (slope(t,r[t],tmp) > slope(t,r[t]-1,r[t])) r[t]--;
else break;
x[t][++r[t]] = X; y[t][r[t]] = Y; pos[t][r[t]] = i;
}

inline double Get(int t, int w){
while (l[t] < r[t]) if (slope(t,l[t],l[t]+1) > rev[w+1]) l[t]++;
else break;
return (arr[w]-arr[pos[t][l[t]]])*rev[w+1]+y[t][l[t]];
}

int main(){
freopen("math.in","r",stdin);
freopen("math.out","w",stdout);
for (int i=1;i<=n;i++) AA[i] = read();
for (int i=1;i<=n;i++) arr[i] = (double)AA[i]+arr[i-1];
for (int i=n;i;i--) rev[i] = rev[i+1] + (double)1/AA[i];
for (int i=1;i<=n;i++) ret += (double)AA[i]*rev[i];
for (int i=0;i<=k;i++) l[i] = 1;

for (int w=1;w<n;w++){
for (int i=1;i<k;i++) if (r[i])
update(i+1,arr[w],Get(i,w),w);
update(1,arr[w],arr[w]*rev[w+1],w);
}
double vout = 0;
for (int i=l[k];i<=r[k];i++)
vout = max(vout, y[k][i]);
printf("%.15lf\n",ret - vout);
return 0;
}