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; }