链接：https://www.luogu.org/problem/P1880
思路：区间dp，只不过是环上的，把整个序列复制一份就好了。
dp[l][r]表示l到r的最大/小值，状态转移方程就是dp[l][r]=max/min{dp[l][k]+dp[k+1][r] | l<=k<r}+sum[r]-sum[l-1],啥意思呢，就是把l到r的区间分成两部分，一部分是l到k，另一部分是k+1到r，( l到r的最值 )就等于( ( l到k的最值 ) 加 ( k+1到r的最值 ) )的最值 再加上 ( l到r的元素和 ) ，具体证明不赘述因为我不会。枚举的时候先枚举区间长度，再枚举区间左端点，最后枚举k的下标，几乎就是区间dp的模板
代码：
1 //
2 // _oo0oo_
3 // o8888888o
4 // 88" . "88
5 // (| -_- |)
6 // 0 = /0
7 // ___/`---'\___
8 // .' \| |// '.
9 // / \||| : |||//
10 // / _||||| -:- |||||-
11 // | | \ - /// | |
12 // | \_| ''---/'' |_/ |
13 // .-\__ '-' ___/-. /
14 // ___'. .' /--.-- `. .'___
15 // ."" '< `.___\_<|>_/___.' >' "".
16 // | | : `- \`.;` _ /`;.`/ - ` : | |
17 // `_. \_ __ /__ _/ .-` / /
18 // =====`-.____`.___ \_____/___.-`___.-'=====
19 // `=---='
20 //
21 //
22 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
23 //
24 // 佛祖保佑 永无BUG
25 //
26 //
27 //
28
29 // #include<bits/stdc++.h>
30 #include<iostream>
31 #include<cstdio>
32 #include<cmath>
33 #include<string>
34 #include<vector>
35 #include<algorithm>
36 #include<queue>
37 #include<deque>
38 #include<stack>
39 #include<map>
40 #include<cstring>
41
42 #define inf 0x3f3f3f3f
43 using namespace std;
44
45 typedef long long ll;
46 typedef long double ld;
47
48 const int M = int(1e5)*3 + 5;
49 const int mod = 10056;
50
51 inline int lowbit(int x) {
52 return x & (-x);
53 }
54
55 int a[M];
56 int sum[M];
57 int dp_max[1005][1005];
58 int dp_min[1005][1005];
59 int minn,maxn;
60 int main()
61 {
62 memset(dp_min,inf,sizeof(dp_min));
63 memset(dp_max,-inf,sizeof(dp_max));
64 int n;cin>>n;
65 for(int i=1;i<=n;i++){
66 cin>>a[i];
67 a[i+n]=a[i];
68 }
69 for(int i=1;i<=n+n;i++){
70 sum[i]=sum[i-1]+a[i];
71 dp_min[i][i]=0;//自己合并自己就是0
72 dp_max[i][i]=0;//自己合并自己就是0
73 }
74
75 for(int len=2;len<=n;len++){
76 for(int l=1;l<=n+n-len+1;l++){
77 int r=l+len-1;
78 for(int k=l;k<r;k++){
79 dp_max[l][r]=max(dp_max[l][r],dp_max[l][k]+dp_max[k+1][r]);
80 dp_min[l][r]=min(dp_min[l][r],dp_min[l][k]+dp_min[k+1][r]);
81 }
82 dp_min[l][r]+=(sum[r]-sum[l-1]);
83 dp_max[l][r]+=(sum[r]-sum[l-1]);
84 }
85 }
86
87 minn=inf;maxn=-inf;
88 for(int i=1;i<=n;i++){
89 minn=min(minn,dp_min[i][i+n-1]);
90 maxn=max(maxn,dp_max[i][i+n-1]);
91 }
92
93 cout<<minn<<endl<<maxn<<endl;
94 return 0;
95 }
备注：急需一名OI爷带我进final