TOJ 277 騎腳踏車 ( Greedy )

http://sprout.tw/oj/pro/277/
很明顯如果希望疲累度最大，就不能讓休息站幫我們太多。讓休息站最沒有幫助的方法無疑是連續的，還有一個起點一個終點的情況。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 6;
const int MAXA = 1e3 + 3;
typedef long long ll;

int n;
int a[ MAXN ];
int pa[ MAXN ];

ll getVal(int lb, int rb){ // [ lb, rb ]
    ll dis = pa[ rb ] - pa[ lb ];
    return dis * dis;
}

void solve(){
    ll ans = getVal( 0, 1 ) + getVal( 1, n - 1 ) + getVal( n - 1, n );
    for(int i = 1; i < n - 1; ++i)
        ans = max<ll>( ans, getVal( 0, i ) + getVal( i, i + 1 ) + getVal( i + 1, n ) );
    printf("%lld\n", ans);
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &a[ i ]);
        pa[ i ] = pa[ i - 1 ] + a[ i ];
    }
    solve();
    return 0;
}