[TIOJ 1636] 錢包的路

作法：

看到範圍就知道不是 n^2 的DP，應該是某種貪心。而直覺上會認為，如果先往右走到一個點再一直左右左右的話會是最好的，感覺如果一直循環的大小是 3 的話，改成循環左邊兩個或是循環右邊兩個會更好，有點類似越少數可以讓平均越高的概念。

這邊給一個大概的證明，若現在在 a_i ，考慮以下三種走法：
1.右左右左 => 2*a_i + 2*a_( i+1 )
2.右右左右 => 2*a_( i+1 ) + 2*a_( i+2 )
3.右右左左 => a_i + 2*a_( i+1 ) + a_( i+2 )
可以看到 3 一定不會同時比 1 和 2 好，所以回頭走兩步是錯的選擇，因此一定是兩個數一直循環是最好的。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1000000+10 ;
LL a[maxn] ;
main()
{
    int n,k ;
    scanf("%d%d",&n,&k) ;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]) ;
    LL sum=0LL , ans=0LL ;
    for(int i=1;i<=n && k+1>=i;i++)
    {
        sum+=a[i] ;
        if(i==1) { ans=a[i] ; continue ; }
        LL val=sum ;
        int num=k-(i-1) ;
        val+= a[i-1]*((num+1)/2) + a[i]*(num/2) ;
        ans=max(ans,val) ;
    }
    if(n==1) printf("%lld\n",((k+1)/2)*a[1]) ;
    else printf("%lld\n",ans) ;
}