美团网站建设,天津做网架公司,如何提高网站在百度的排名,域名地址题目链接
[NOI1995] 石子合并
题目描述
在一个圆形操场的四周摆放 N N N 堆石子#xff0c;现要将石子有次序地合并成一堆#xff0c;规定每次只能选相邻的 2 2 2 堆合并成新的一堆#xff0c;并将新的一堆的石子数#xff0c;记为该次合并的得分。
试设计出一个算法…题目链接
[NOI1995] 石子合并
题目描述
在一个圆形操场的四周摆放 N N N 堆石子现要将石子有次序地合并成一堆规定每次只能选相邻的 2 2 2 堆合并成新的一堆并将新的一堆的石子数记为该次合并的得分。
试设计出一个算法,计算出将 N N N 堆石子合并成 1 1 1 堆的最小得分和最大得分。
输入格式
数据的第 1 1 1 行是正整数 N N N表示有 N N N 堆石子。
第 2 2 2 行有 N N N 个整数第 i i i 个整数 a i a_i ai 表示第 i i i 堆石子的个数。
输出格式
输出共 2 2 2 行第 1 1 1 行为最小得分第 2 2 2 行为最大得分。
样例 #1
样例输入 #1
4
4 5 9 4样例输出 #1
43
54提示 1 ≤ N ≤ 100 1\leq N\leq 100 1≤N≤100 0 ≤ a i ≤ 20 0\leq a_i\leq 20 0≤ai≤20。
算法思想
每次只能选相邻的 2 2 2 堆合并成新的一堆以每次合并为阶段进行区间型动态规划以最小得分为例
状态表示 f [ i ] [ j ] f[i][j] f[i][j]表示从第 i i i堆石子一直合并到第 j j j堆石子的最小得分状态计算根据最后一次合并的位置可以分为下面几种情况 将第 i i i堆石子和后面已经完成的 [ i 1... j ] [i1...j] [i1...j]这堆石子合并得到的分数为 f [ i ] [ i ] f [ i 1 ] [ j ] s [ i . . . j ] f[i][i]f[i1][j]s[i...j] f[i][i]f[i1][j]s[i...j]将前面已经完成合并的 [ i . . . i 1 ] [i...i1] [i...i1]这堆石子和后面已经完成的 [ i 2... j ] [i2...j] [i2...j]这堆石子合并得到的分数为 f [ i ] [ i 1 ] f [ i 2 ] [ j ] s [ i . . . j ] f[i][i1]f[i2][j]s[i...j] f[i][i1]f[i2][j]s[i...j]…将前面已经完成合并的 [ i . . . k ] [i...k] [i...k]这堆石子和后面已经完成的 [ k 1... j ] [k1...j] [k1...j]这堆石子合并得到的分数为 f [ i ] [ i 1 ] f [ i 2 ] [ j ] s [ i . . . j ] f[i][i1]f[i2][j]s[i...j] f[i][i1]f[i2][j]s[i...j]…将前面已经完成合并的 [ i . . . j − 1 ] [i...j-1] [i...j−1]这堆石子和第 j j j堆石子合并得到的分数为 f [ i ] [ j − 1 ] f [ j ] [ j ] s [ i . . . j ] f[i][j-1]f[j][j]s[i...j] f[i][j−1]f[j][j]s[i...j] f [ i ] [ j ] f[i][j] f[i][j]为以上情况的最小值。其中 s [ i . . . j ] s[i...j] s[i...j]表示本次合并得到的分数也就是第 i i i堆石子到第 j j j堆石子的分数和可以使用前缀和计算得到。
初始状态为计算最小值 f [ i ] [ j ] f[i][j] f[i][j]应初始化为无穷大 f [ i ] [ i ] f[i][i] f[i][i]表示就合并自己初始值为0。
除此之外由于是在一个圆形操场的四周摆放 N N N 堆石子也就是说可以从任何一点出发进行合并。因此需要采用拆环为链的方式进行处理最后求以任意起点开始分数的最小值。
时间复杂度
状态数为 n × n n\times n n×n状态计算时需要枚举最后一次合并位置因此时间复杂度为 O ( n 3 ) O(n^3) O(n3)。
代码实现
#include iostream
#include cstring
#include algorithm
using namespace std;
const int N 110 * 2, INF 0x3f3f3f3f;
int f[N][N], g[N][N];
int a[N], s[N];int main()
{int n;cin n;for(int i 1; i n; i ) {cin a[i];a[n i] a[i]; //拆环为链}//计算前缀和for(int i 1; i 2 * n; i ) s[i] s[i - 1] a[i];//枚举每次合并的长度最小长度为2 for(int len 2; len n; len )for(int i 1; i len - 1 2 * n; i ) //枚举开始合并的位置{int j i len - 1; //合并结束的位置f[i][j] INF; //初始状态//枚举最后一次合并的位置kfor(int k i; k j; k ){f[i][j] min(f[i][j], f[i][k] f[k 1][j] s[j] - s[i - 1]); //最小得分g[i][j] max(g[i][j], g[i][k] g[k 1][j] s[j] - s[i - 1]); //最大得分}}int minx 1e9, maxx 0;for(int i 1; i n; i ) //枚举合并起点{minx min(minx, f[i][i n - 1]);maxx max(maxx, g[i][i n - 1]);}cout minx \n maxx;return 0;
}
