思路讲解
注意石子是一个圈，这个时候化曲为直，化为长度为两倍的序列
然后区间dp一般是O(n**3)的，因为序列的合并可能发生在任何地方，不一定是头和尾
AC代码
AC https://www.luogu.com.cn/record/197959001
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| #include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
typedef long long ll;
typedef std::pair<ll,ll> pll;
typedef std::array<ll,3> arr;
const ll MAXN=217;
ll N,T,A[MAXN],dp_min[MAXN][MAXN],dp_max[MAXN][MAXN],sumA[MAXN];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);std::cout.tie(0);
std::cin>>N;
for(int i=1;i<=N;++i){
std::cin>>A[i];
sumA[i]=A[i]+sumA[i-1];
}
for(int i=N+1;i<=2*N;++i){
A[i]=A[i-N];
sumA[i]=A[i]+sumA[i-1];
}
for(int i=1;i<=2*N;++i){
dp_min[i][i] = 0;
dp_max[i][i] = 0;
}
for(int len=2;len<=N;++len){
for(int i=1;i<=2*N-len+1;++i){
int j = i + len - 1;
dp_min[i][j] = 1e18+7;
dp_max[i][j] = 0;
for(int k=i;k<j;++k){
ll cost = sumA[j] - sumA[i-1];
dp_min[i][j] = std::min(dp_min[i][j], dp_min[i][k] + dp_min[k+1][j] + cost);
dp_max[i][j] = std::max(dp_max[i][j], dp_max[i][k] + dp_max[k+1][j] + cost);
}
}
}
ll min_ans = 1e18+7;
ll max_ans = 0;
for(int i=1;i<=N;++i){
min_ans = std::min(min_ans, dp_min[i][i+N-1]);
max_ans = std::max(max_ans, dp_max[i][i+N-1]);
}
std::cout<<min_ans<<"\n";
std::cout<<max_ans<<"\n";
return 0;
}
|
心路历程（WA，TLE，MLE……）
WA
https://www.luogu.com.cn/record/197954954
序列的合并可能发生在任何地方，不一定是头和尾
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| #include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
typedef long long ll;
typedef std::pair<ll,ll> pll;
typedef std::array<ll,3> arr;
const ll MAXN=217;
ll N,T,A[MAXN],dp[MAXN][MAXN],sumA[MAXN];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);std::cout.tie(0);
std::cin>>N;
for(int i=1;i<=N;++i){
std::cin>>A[i];
sumA[i]=A[i]+sumA[i-1];
}
for(int i=N+1;i<=2*N;++i){
A[i]=A[i-N];
sumA[i]=A[i]+sumA[i-1];
}
for(int i=2*N;i>=1;--i){
for(int j=i+1;j<=2*N;++j){
dp[i][j]=std::min(dp[i+1][j]+sumA[j]-sumA[i]+A[i],
dp[i][j-1]+sumA[j-1]-sumA[i-1]+A[j]);
}
}
ll ans=1e18+7;
for(int i=1;i<=N;++i){
ans=std::min(dp[i][i+N-1],ans);
}
std::cout<<ans<<"\n";
std::memset(dp, 0, sizeof(dp));
for(int i=2*N;i>=1;--i){
for(int j=i+1;j<=2*N;++j){
dp[i][j]=std::max(dp[i+1][j]+sumA[j]-sumA[i]+A[i],
dp[i][j-1]+sumA[j-1]-sumA[i-1]+A[j]);
}
}
ans=0;
for(int i=1;i<=N;++i){
ans=std::max(dp[i][i+N-1],ans);
}
std::cout<<ans<<"\n";
return 0;
}
|