题目传送门:http://pan.baidu.com/s/1eRRG6Wy
离线版题目:http://paste.ubuntu.com/18459243/
数据传送门:http://pan.baidu.com/s/1miarNuS
这一道题目,真的是十分可惜。考试前一个小时,码完了O(K*n^2) 的暴力DP,但一直到考试结束前9分钟才推出斜率DP的式子。
本来以为斜率DP可以随便切了QAQ,现在来看,代码实现确实不恼火了,但是推式子还是很恼火啊!
这一道题目,式子推出来之后,也就没什么好说的了。先贴一贴斜率DP的代码,后续再来更决策单调,和神奇的二分的代码。
#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];
inline int read(){
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);
n = read(); k = read()-1;
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;
}