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;
}