14157: 【原4157】水灯节

题目

题目描述

author: Yifan 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4157

Description

水灯节到了，面包正忙着挂水灯。现在有n个水灯依次挂在一条绳子上，第i个水灯离地面的高度是\(H_i\)（\(H_i\)是实数）。由于重力的缘故，每个水灯的高度比左右相邻水灯高度的平均值低1个高度单位，即对任意\(1 < i < n\)，\(H_i = \frac{H_{i - 1} + H_{i + 1}}{2} - 1\)。规定水灯不能触地，即任意\(1 \le i \le n\)，\(H_i \ge 0\)。现在已知\(H_1\)，求\(H_n\)的最小值。

Input Format

一行，一个正整数n和一个实数\(H_1\)。

Output Format

一个实数，表示\(H_n\)的最小值。

Sample Input

8 15

Sample Output

9.75

Data Range

对于20%的数据，\(3 \le n \le 10\)，\(10 \le H_1 \le 100\)。

对于50%的数据，\(3 \le n \le 100\)，\(10 \le H_1 \le 500\)。

对于100%的数据，\(3 \le n \le 1000\)，\(10 \le H_1 \le 1000\)。

Hint

第二个水灯是面包最喜欢的，所以他很在意把第二个水灯挂多高。

zqy2018's solution

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n;
double h1;
ll a[1005], b[1005], c[1005];
void init(){
    n = read();
    cin >> h1;
    a[1] = c[1] = 0, b[1] = 1;
    a[2] = 1, b[2] = c[2] = 0;
}
void solve(){
    double h2 = 0;
    for (int i = 3; i <= n; ++i){
        a[i] = 2 * a[i - 1] - a[i - 2], 
        b[i] = 2 * b[i - 1] - b[i - 2], 
        c[i] = 2 * c[i - 1] - c[i - 2] + 2;
        h2 = max(h2, (-b[i] * h1 - c[i]) / a[i]);
    }
    double res = a[n] * h2 + b[n] * h1 + c[n];
    printf("%.2lf\n", res);                     // warning
}
int main(){
    init();
    solve();
    return 0;
}