题目来源：ABC326-E

DQ-3 Maximize Rating

题目信息

题面翻译

高桥君参加了 场比赛，第 场比赛的表现是 分。

高桥君要选择至少一场比赛来计算等级分，设选择的第 场比赛的表现是 ，总共选择了 场比赛来计算，那么最终的等级分为 。

设计一个程序来计算最终的等级分的最大值是多少，你的输出与标准答案的相对或绝对误差小于 即被视为正确。

题目描述

高橋君は回コンテストに参加し、回目に参加したコンテストにおいてパフォーマンスを獲得しました。
高橋君はこの中から (つ以上) いくつかのコンテストを選び、それらの結果から計算される高橋君のレートを最大にしたいと考えています。

コンテストをうまく選んだとき、高橋君のレートとしてあり得る最大の値を求めてください。

ただし、高橋君のレートは、高橋君の選んだコンテストの数が個であり、 選んだコンテストにおけるパフォーマンスが 参加した順に それぞれであるとき、

によって計算されます。

输入格式

入力は以下の形式で標準入力から与えられる。

输出格式

高橋君のレートとしてあり得る最大の値を出力せよ。
出力は、真の値との絶対誤差または相対誤差が以下のとき正解と判定される。

样例 #1

样例输入 #1

3
1000 600 1200

样例输出 #1

256.735020470879931

样例 #2

样例输入 #2

3
600 1000 1200

样例输出 #2

261.423219407873376

样例 #3

样例输入 #3

1
100

样例输出 #3

-1100.000000000000000

提示

制約

• 入力はすべて整数

Sample Explanation 1

高橋君が回目と回目のコンテストを選んだ時、レートは、となり、この時レートが最大となります。

Sample Explanation 2

回目のコンテストすべてを選んだとき、レートが最大となります。

Sample Explanation 3

レートは負になることもあります。

题目分析：

首先讨论这个题目的函数方程：

不难发现这是一个很经典的问题，针对第个数，有选择与不选择两种选法。

但是，直接运算会很困难。所以，可以只对上半部分进行:

注意大限制为从到选个数字，所以

AC代码

#include<bits/stdc++.h>
using namespace std;
int n;
double dp[5001][5001];
double a[5001];
double nine[5001];
void init()
{
    nine[0]=1;
    for(int i=1;i<=n;i++)
    {
        nine[i]=nine[i-1]*0.9;
    }
}
double maxn(double a,double b)
{
    if(b-a>(1e-6))return b;
    else return a;
}
int main()
{
    cin>>n;
    init();
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=maxn(dp[i-1][j-1]*0.9+a[i],dp[i-1][j]);
        }
    }
    double ans=-1e10;
    for(int i=1;i<=n;i++)
    {
        ans=maxn(dp[n][i]/(10-10*nine[i])-(1200/sqrt(i)),ans);
    }
    cout<<fixed<<setprecision(15)<<ans<<endl;
    system("pause");
    return 0;
}