题意:
N个点,每个点离X轴的距离满足如下关系:
H1 = A
Hi = (Hi-1 + Hi+1)/2 - 1, for all 1 < i < N
HN = B
Hi >= 0, for all 1 <= i <= N
一直A,求B的最小值。
题解:
由递推关系式可以知道,确定H2,剩下的所有H都可以确定,二分求H2的最小,进而得出HN的最小即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<vector>
#include<functional>using namespace std;
int maxl=1000;int N;
double A,B,h[1005];bool C(double mid)
{h[1]=mid;for(int i=2;i<N;i++){h[i]=2*h[i-1]+2-h[i-2];if(h[i]<0)return false;}B=h[N-1];return true;
}int main()
{cin>>N>>A;h[0]=A;//对第二个点进行二分double lb=-1,ub=maxl+2;for(int i=1;i<=100;i++){double mid=(lb+ub)/2;if(C(mid))ub=mid;//最小化可行解else lb=mid;}printf("%.2f",B);//poj g++不能lf,C++可以lf 玄学!
}