题解报告：hdu 2086 A1 = ?

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2086

Problem Description

有如下方程：A_i = (A_i-1 + A_i+1)/2 - C_i (i = 1, 2, 3, .... n). 若给出A₀, A_n+1, 和 C₁, C₂, .....C_n. 请编程计算A₁ = ?

Input

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

Output

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

Sample Input

50.00 25.00

10.00

50.00 25.00

10.00

20.00

Sample Output

27.50 15.00

解题思路：这是一道纯找规律的数学题，经过推算有：

n=1 2A1=A0+A2-2C1

n=2 3A1=2A0+A3-4C1-2C2

n=3 4A1=3A0+A4-6C1-4C2-2C3

n=4 5A1=4A0+A5-8C1-6C2-4C3-2C4

... ......

n=n (n+1)A1=nA0+A(n+1)-(2*n)C1-...-2Cn

AC代码：（注意这里用C语言的输入输出，不然会TLE-_-||(109ms过)）

 #include<bits/stdc++.h>

 using namespace std;

 double a[],c[];

 int main()

 {

     int n,k;

     double sum;

     while(~scanf("%d",&n)){

         memset(a,,sizeof(a));//清零

         scanf("%lf %lf",&a[],&a[n+]);

         for(int i=;i<=n;i++)

             scanf("%lf",&c[i]);//赋值

         sum=,k=;

         for(int i=n;i>;i--){//计算Cn前n项和

             c[i]*=k;

             k+=;

             sum+=c[i];

         }

         printf("%.2f\n",1.0/(n+)*(a[n+]+n*a[]-sum));//推导公式

     }

     return ;

 }

巴特西

题解报告：hdu 2086 A1 = ?

最新文章

热门文章