P1880 [NOI1995]石子合并【区间dp】
P1880 [NOI1995]石子合并
提交 42.29k
通过 19.06k
时间限制 1.00s
内存限制 125.00MB
标签
进入讨论版
相关讨论
推荐题目
题目描述
在一个圆形操场的四周摆放 NNN 堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个算法,计算出将 NNN 堆石子合并成 111 堆的最小得分和最大得分。
输入格式
数据的第 111 行是正整数 NNN，表示有N堆石子。
第 222 行有 NNN 个整数，第 iii 个整数 aia_iai 表示第 iii 堆石子的个数。
输出格式
输出共 222 行，第 111 行为最小得分，第 222 行为最大得分。
输入输出样例
输入 #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 }
查看19道真题和解析
