Link

Question

给出 \(N\) 个数 \(Q_i\)，从中按照顺序选出 \(k\) 个数，使得

\[R=\frac{\sum^k_{i=1}(0.9)^{k-i}\times Q_i}{\sum^k_{i=1}(0.9)^{k-i}}-\frac{1200}{\sqrt{k}} \]

最大。

\(N \le 5000\)

Solution

观察到可以 \(N^2\) 做

考虑如果 \(k\) 固定的话，那么 \(\sum^k_{i=1}(0.9)^{k-i}\) 和 \(\frac{1200}{\sqrt{k}}\) 就固定了，现在就需要求最大的 \(\sum^k_{i=1}(0.9)^{k-i}\times Q_i\)

观察到连乘的性质，考虑动态规划

定义 \(F[i][k]\) 表示，前 \(i\) 个数字，已经取了 \(k\) 个的最大值。

如果取第 \(i\) 个数字，那么转移方程就是 \(F[i][k]=F[i-1][k-1] \times 0.9 +Q_i\)

如果不取就是 \(F[i-1][k]\)

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
int N;
double F[maxn][maxn]; //F[i][k] 表示前 i 个数字，已经选了 k 个最大值
double sumk[maxn],a[maxn];
int main(){
    freopen("E.in","r",stdin);
    cin>>N;
    for(int i=1;i<=N;i++) cin>>a[i];
    for(int i=1;i<=N;i++)
    for(int k=1;k<=i;k++){
        F[i][k]=max(F[i-1][k],F[i-1][k-1]*0.9+a[i]);
    }
    double ans=-1000000;
    for(int k=1;k<=N;k++){
        sumk[k]=sumk[k-1]*0.9+1;
        double now=F[N][k]*1.0/sumk[k]-1200.0/sqrt(k);
        ans=max(ans,now);
    }
    printf("%.10lf",ans);
    return 0;
}