感受到了生活的艰辛QAQ...这才是真正的爆锤啊...（因为t1t3还没有理解所以只能贴t2叻QAQ
区间DP...爆哭把题理解错了，以为随着拿的东西越来越多，断点也会越来越多，出现可以选很多的情况QAQ，然而是不会的，自始至终只会有一个断点，哥哥和妹妹取都只有两个方向，而妹妹还是强制选择的QAQ。
所以把环展开就是一个区间DP叻，枚举长度（长度作为层数）、区间，因为是从长度小的转移到长度多的，区间根据长度的奇偶性可以判断当前该谁拿，如果是妹妹，就在两端取大的更新区间（不加dp值），如果是哥哥就往两边都更新。
#include<iostream> #include<cstdio> #include<cstring> #define LL long long using namespace std; LL dp[4005][4005], a[4005]; int n; int main ( ) { freopen ( "cake.in", "r", stdin ); freopen ( "cake.out", "w", stdout ); scanf ( "%d", &n ); for ( int i = 1; i <= n; i ++ ) scanf ( "%d", &a[i] ), a[i+n] = a[i]; int nn = n << 1; memset ( dp, -1, sizeof ( dp ) ); for ( int i = 1; i <= nn; i ++ ) dp[i][i] = a[i]; for ( int len = 1; len <= n; len ++ ) for ( int i = 2; i < nn - len + 1; i ++ ) { int j = i + len - 1; if ( dp[i][j] > 0 ) { if ( len & 1 ) { if ( a[i-1] < a[j+1] ) dp[i][j+1] = max ( dp[i][j+1], dp[i][j] ); else dp[i-1][j] = max ( dp[i-1][j], dp[i][j] ); } else { dp[i-1][j] = max ( dp[i-1][j], dp[i][j] + a[i-1] ); dp[i][j+1] = max ( dp[i][j+1], dp[i][j] + a[j+1] ); } } } LL ans = 0; for ( int i = 1; i <= nn - n + 1; i ++ ) ans = max ( ans, dp[i][i+n-1] ); printf ( "%I64d", ans ); return 0; }
虽然题没有改完，但是杀了只猪都不吃风风吹牛羊槽鸭鸡！！！！！！！rzrzrzrzrzrzrzrzrzrzrzrzrzrzrzrzrzrz_Ruben笨