P1880 [NOI1995]石子合并

提交 42.29k

通过 19.06k

时间限制 1.00s

内存限制 125.00MB

题目提供者 JosephZheng

难度普及+/提高

历史分数100

提交记录

查看题解

题目描述

在一个圆形操场的四周摆放

试设计出一个算法,计算出将

输入格式

数据的第

第 $aia_iai 表示第 iii 堆石子的个数。$

输出格式

输出共

输入输出样例

输入 #1

4
4 5 9 4

输出 #1

43
54

说明/提示

$1≤N≤1001\leq N\leq 1001≤N≤100，0≤ai≤200\leq a_i\leq 200≤ai≤20。$

$思路$

$区间DP，化链为环，在1~n的区间长度内枚举区间左右端点，在 i~j 的范围内枚举分割线k；$

$转移方程：$

$min_f[i][j] = min(min_f[i][j], min_f[i][k] + min_f[k + 1][ j ] + sum[ j ] - sum[ i-1]); max_f[i][j] = max(max_f[i][j], max_f[i][k] + max_f[k + 1][ j ] + sum[ j ] - sum[ i-1 ]);$

$CODE$

 1 #include <bits/stdc++.h>
 2 #define dbg(x) cout << #x << "=" << x << endl
 3 
 4 using namespace std;
 5 using LL = long long;
 6 
 7 template<class T>inline void read(T &res)
 8 {
 9     char c;T flag=1;
10     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
11     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
12 }
13 
14 namespace _buff {
15     const size_t BUFF = 1 << 19;
16     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
17     char getc() {
18         if (ib == ie) {
19             ib = ibuf;
20             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
21         }
22         return ib == ie ? -1 : *ib++;
23     }
24 }
25 
26 int qread() {
27     using namespace _buff;
28     int ret = 0;
29     bool pos = true;
30     char c = getc();
31     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
32         assert(~c);
33     }
34     if (c == '-') {
35         pos = false;
36         c = getc();
37     }
38     for (; c >= '0' && c <= '9'; c = getc()) {
39         ret = (ret << 3) + (ret << 1) + (c ^ 48);
40     }
41     return pos ? ret : -ret;
42 }
43 
44 const int maxn = 1e5 + 7;
45 const int inf  = 0x3f3f3f3f;
46 
47 int n;
48 int a[maxn];
49 int min_f[207][207];
50 int max_f[207][207];
51 int sum[maxn];
52 
53 int main()
54 {
55     read(n);
56     for(int i = 1; i <= n; ++i) {
57         read(a[i]);
58         a[i+n] = a[i];
59     }
60     int m = n * 2;
61     for(int i = 1; i <= m; ++i) {
62         sum[i] = sum[i-1] + a[i];
63         //printf("sum[%d]:%d\n",i,sum[i]);
64     }
65     memset(min_f, inf, sizeof(min_f));
66 
67     for(int i = 1; i <= m; ++i) {
68         min_f[i][i] = 0;
69     }
70     for(int len = 2; len <= n; ++len) {///长度
71         for(int i = 1; i <= m-len+1; ++i) {///左
72             int j = i + len - 1;///右
73             for(int k = i; k < j; ++k) {///分割
74                 min_f[i][j] = min(min_f[i][j], min_f[i][k]+min_f[k+1][j]+sum[j]-sum[i-1]);
75                 max_f[i][j] = max(max_f[i][j], max_f[i][k]+max_f[k+1][j]+sum[j]-sum[i-1]);
76             }
77         }
78     }
79     int minn = 0x7fffffff, maxx = -1;
80     for(int i = 1; i <= n; ++i) {
81         minn = min(min_f[i][i+n-1],minn);
82         maxx = max(max_f[i][i+n-1],maxx);
83     }
84     printf("%d\n%d\n",minn,maxx);
85     return 0;
86 }

View Code

P1880 [NOI1995]石子合并【区间dp】