今天学DP，因为学过，感觉挺简单。
但是下午比赛错了一道DP题，状态转移方程有点多，代码如下

#include
using namespace std;
int n,a[1000010],dp[1000010][4][2];
int main(){
    freopen("fruit.in","r",stdin);
    freopen("fruit.out","w",stdout);
    cin>>n;
    for(int i=1;i>a[i];
    }
    for(int i=0;i<=n;i++){
        for(int j=1;j<4;j++){
            for(int k=0;k0)dp[i][j][k]=-100000000;
            }
        }
    }
    dp[0][0][0]=0;
    for(int j=1;j<4;j++){
        for(int i=1;i<=n;i++){
            dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
            dp[i][j][1]=max(dp[i-1][j][1]+a[i],dp[i][j][1]);
            dp[i][j][1]=max(max(dp[i-1][j-1][0],dp[i-1][j-1][1])+a[i],dp[i][j][1]);
        }
    }
    cout<<max(dp[n][3][0],dp[n][3][1]);
    return 0;
}