hdu2086A1 = ?解题报告---推导求通项

A1 = ?

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11271    Accepted Submission(s): 6771

 

Problem Description

有如下方程：Ai = (Ai-1 + Ai+1)/2 - Ci (i = 1, 2, 3, .... n).
若给出A0, An+1, 和 C1, C2, .....Cn.
请编程计算A1 = ?

Input

输入包括多个测试实例。
对于每个实例，首先是一个正整数n,(n <= 3000); 然后是2个数a0, an+1.接下来的n行每行有一个数ci(i = 1, ....n);输入以文件结束符结束。

Output

对于每个测试实例，用一行输出所求得的a1(保留2位小数).

Sample Input

1

50.00

25.00

10.00

2

50.00

25.00

10.00

20.00

Sample Output

27.50

15.00

推导过程：

n = 1：可以直接看出     2a1 = 2a0+a2 -2c1

n = 2:两个式子推导：

1.ai = (ai-1+ai+1)/2 - ci   2.ai+1 = (ai+ai+2)/2 - ci+1

得到：    3ai = 2ai-1 + ai+2 - 4ci - 2ci+1

所以        3a1 = 2a0 + a3 -4c1 - 2c2;

n=3：三个式子去推导：ai, ai+1,ai+2

得到        4a1 = 3a0 + a4 - 6c1 - 4c2 - 2c3

Code:

#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<list>
#define mod 998244353
#define INF 0x3f3f3f3f
#define Min 0xc0c0c0c0
#define mst(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i=a;i<b;i++)
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
double res;
void get_a1(double a[], double c[], int n){
    double x1 = n * a[0] + a[n + 1];
    double x2 = 0;
    for(int i = 1; i <= n; i++){
        x2 += 2 * (n - i + 1) * c[i];
    }
    res = (x1 - x2) / (n + 1);
}
int main(){
   int n;
   while(scanf("%d", &n) != EOF){
        if(n == -1) break;
        double a[3005] = {0}, c[3005] = {0};
        scanf("%lf%lf", &a[0], &a[n + 1]);
        for(int i = 1; i <= n; i++){
            scanf("%lf", &c[i]);
        }
        get_a1(a, c, n);
        printf("%.2lf\n", res);
   }
   return 0;
}