POJ 2601 Simple calculations - Area1のif(memo[i][j])

問題

$a_i = (a_{i-1} + a_{i+1})/2 - c_i$ という漸化式の数列がある。 $a_0,a_{n+1},c_1,..c_n$ が与えられるので $a_1$ を求めよ。

やりかた

(たぶん嘘解法)
$a_1$ に対して $a_{n+1}$ がmonotonicalに変化するから $a_1$ に関して二分探索すればいいんじゃまいか(・∀・)!!
で通ってしまった。よく考えるとmonotonicalじゃないような。
実験すると一般項がわかるのでそれでやるのがいいと思う。

以下ソース。

//嘘解法っぽい
int n;
double b, a[3010];
double c[3010];
int main(int argc, char **argv){
  scanf("%d", &n);
  scanf("%lf", &a[0]);
  scanf("%lf", &b);
  for(int i = 1; i <= n; i++)
    scanf("%lf", c + i);
  
  double ub = 1001, lb = -1001;
  for(int i = 0; i < 100; i++){
   a[1] = (ub + lb) / 2;
   for(int i = 2; i <= n + 1; i++)
     a[i] = 2.0 * a[i - 1] - a[i - 2] + 2.0 * c[i - 1];
   if(b > a[n + 1]) lb = a[1];
   else ub = a[1];
  }
  printf("%.2lf\n", a[1]);
  return 0;
}