COGS 1191. [Tyvj Feb11] 猫咪的进化

★   输入文件：neko.in   输出文件：neko.out   简单对比
时间限制：1 s   内存限制：128 MB

【背景】

对于一只猫咪来说，它是有九条命的。但是并不是所有的猫咪都是这样，只有那些造化很高的猫咪才能死而复生。而且对于这样的猫咪，如果它能够活到第九条命，那么它最终可以变成任何一种它想成为的动物（当然也可以继续做猫咪啦），我们称这样的猫咪为猫神。现在一只获得了进化机会的猫咪，受到了女神snowharmony的考验。

【题目描述】

它拥有t个单位的时间，在每个单位时间里，它可以选择沉默、叫一声“喵”、或者叫两声“喵喵”。对于每个单位时间，均有一个实数v[i]，猫咪叫一声可获得v[i]的进化量，叫两声可以获得(v[i])^2的进化量，然而它在某个单位时间如果叫了两声，下一单位时间必须保持沉默来休息。
女神Snowharmony要求它以一定的方式叫，只有它最终获得了最大的进化量，它才能进化为猫神，从而变为它想成为的动物——人族zsw95。
请你帮助它计算最大进化量，使他进化为为猫神zsw95。

【输入格式】

输入：
第一行一个整数t。
第二行，t个实数v[i]。

【输出格式】

最大的进化量，保留四位小数。

【样例输入】

3

9 2 1

【样例输出】

82.0000

【提示】

各个测试点1s

1<=t<=800000,-255.00<=v[i]<=255.00
计算结果不超过maxlongint

【来源】

来源：lydliyudong    Tyvj February二月月赛第二场  第1道

dp

屠龙宝刀点击就送

#include <iostream>

#include <cstdio>

#define N 800005

using namespace std;

int t;

double res,v,f[N];

int Main()

{

    freopen("neko.in","r",stdin);

    freopen("neko.out","w",stdout);

    scanf("%d",&t);

    for(int i=;i<=t+;++i) f[i]=-;

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

    {

        scanf("%lf",&v);

        f[i]=max(f[i],f[i-]);

        f[i]=max(f[i],f[i-]+v);

        f[i+]=max(f[i+],f[i-]+v*v);

        res=max(res,f[i]);

    }

    printf("%.4lf",max(res,f[t+]));

    return ;

}

int sb=Main();

int main(int argc,char *argv[]){;}