做文案的网站有些什么,wordpress竖版图片,博客和网站有什么不同,oa系统哪个品牌好题目链接
[NOIP2006 提高组] 能量项链
题目描述
在 Mars 星球上#xff0c;每个 Mars 人都随身佩带着一串能量项链。在项链上有 N N N 颗能量珠。能量珠是一颗有头标记与尾标记的珠子#xff0c;这些标记对应着某个正整数。并且#xff0c;对于相邻的两颗珠子#xff0…题目链接
[NOIP2006 提高组] 能量项链
题目描述
在 Mars 星球上每个 Mars 人都随身佩带着一串能量项链。在项链上有 N N N 颗能量珠。能量珠是一颗有头标记与尾标记的珠子这些标记对应着某个正整数。并且对于相邻的两颗珠子前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样通过吸盘吸盘是 Mars 人吸收能量的一种器官的作用这两颗珠子才能聚合成一颗珠子同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 m m m尾标记为 r r r后一颗能量珠的头标记为 r r r尾标记为 n n n则聚合后释放的能量为 m × r × n m \times r \times n m×r×nMars 单位新产生的珠子的头标记为 m m m尾标记为 n n n。
需要时Mars 人就用吸盘夹住相邻的两颗珠子通过聚合得到能量直到项链上只剩下一颗珠子为止。显然不同的聚合顺序得到的总能量是不同的请你设计一个聚合顺序使一串项链释放出的总能量最大。
例如设 N 4 N4 N4 4 4 4 颗珠子的头标记与尾标记依次为 ( 2 , 3 ) ( 3 , 5 ) ( 5 , 10 ) ( 10 , 2 ) (2,3)(3,5)(5,10)(10,2) (2,3)(3,5)(5,10)(10,2)。我们用记号 ⊕ \oplus ⊕ 表示两颗珠子的聚合操作 ( j ⊕ k ) (j \oplus k) (j⊕k) 表示第 j , k j,k j,k 两颗珠子聚合后所释放的能量。则第 4 4 4 1 1 1 两颗珠子聚合后释放的能量为 ( 4 ⊕ 1 ) 10 × 2 × 3 60 (4 \oplus 1)10 \times 2 \times 360 (4⊕1)10×2×360。
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ( ( ( 4 ⊕ 1 ) ⊕ 2 ) ⊕ 3 ) 10 × 2 × 3 10 × 3 × 5 10 × 5 × 10 710 (((4 \oplus 1) \oplus 2) \oplus 3)10 \times 2 \times 310 \times 3 \times 510 \times 5 \times 10710 (((4⊕1)⊕2)⊕3)10×2×310×3×510×5×10710。
输入格式
第一行是一个正整数 N N N 4 ≤ N ≤ 100 4 \le N \le 100 4≤N≤100表示项链上珠子的个数。第二行是 N N N 个用空格隔开的正整数所有的数均不超过 1000 1000 1000。第 i i i 个数为第 i i i 颗珠子的头标记 1 ≤ i ≤ N 1 \le i \le N 1≤i≤N当 i N iN iN 时第 i i i 颗珠子的尾标记应该等于第 i 1 i1 i1 颗珠子的头标记。第 N N N 颗珠子的尾标记应该等于第 1 1 1 颗珠子的头标记。
至于珠子的顺序你可以这样确定将项链放到桌面上不要出现交叉随意指定第一颗珠子然后按顺时针方向确定其他珠子的顺序。
输出格式
一个正整数 E E E E ≤ 2.1 × 1 0 9 E\le 2.1 \times 10^9 E≤2.1×109为一个最优聚合顺序所释放的总能量。
样例 #1
样例输入 #1
4
2 3 5 10样例输出 #1
710算法思想
根据题目描述测试样例的合并过程如下 由于只能合并相邻两个珠子因此可以使用区间型动态规划的思想进行处理。
状态表示 f [ i ] [ j ] f[i][j] f[i][j]表示从第 i i i颗珠子一直合并到第 j j j颗珠子释放的最大能量
状态计算
从最小的聚合长度 2 2 2开始计算以每次聚合为阶段枚举聚合的起点根据最后一次聚合的位置可以分为下面几种情况 最后一次在 i i i位置聚合即将第 i i i颗珠子和后面的 [ i 1... j ] [i1...j] [i1...j]珠子聚合得到的分数为 f [ i ] [ i ] f [ i 1 ] [ j ] s [ i ] × s [ i 1 ] × r [ j ] f[i][i]f[i1][j]s[i]\times s[i1]\times r[j] f[i][i]f[i1][j]s[i]×s[i1]×r[j] 最后一次在 i 1 i1 i1位置聚合即将前面的 [ i . . . i 1 ] [i...i1] [i...i1]颗珠子和后面的 [ i 2... j ] [i2...j] [i2...j]颗珠子聚合得到的分数为 f [ i ] [ i 1 ] f [ i 2 ] [ j ] s [ i ] × s [ i 2 ] × r [ j ] f[i][i1]f[i2][j]s[i]\times s[i2]\times r[j] f[i][i1]f[i2][j]s[i]×s[i2]×r[j] … 最后一次在 k k k位置聚合即将前面的 [ i . . . k ] [i...k] [i...k]颗珠子和后面的 [ k 1... j ] [k1...j] [k1...j]颗珠子聚合得到的分数为 f [ i ] [ i k ] f [ k 1 ] [ j ] s [ i ] × s [ k 1 ] × r [ j ] f[i][ik]f[k1][j]s[i]\times s[k1]\times r[j] f[i][ik]f[k1][j]s[i]×s[k1]×r[j] … 最后一次在 j − 1 j-1 j−1位置聚合即将前面的 [ i . . . j − 1 ] [i...j-1] [i...j−1]颗珠子和第 j j j颗珠子聚合得到的分数为 f [ i ] [ j − 1 ] f [ j ] [ j ] s [ i ] × s [ j ] × r [ j ] f[i][j-1]f[j][j]s[i]\times s[j]\times r[j] f[i][j−1]f[j][j]s[i]×s[j]×r[j] f [ i ] [ j ] f[i][j] f[i][j]为以上情况的最大值。其中 s [ i ] s[i] s[i]表示第 i i i颗能量珠的头标记 r [ j ] r[j] r[j]表示第 j j j颗能量珠的尾标记 s [ i ] × s [ j ] × r [ j ] s[i]\times s[j]\times r[j] s[i]×s[j]×r[j]表示将两堆能量珠聚合释放的能量。
初始状态
为计算最大值 f [ i ] [ j ] f[i][j] f[i][j]应初始化 0 0 0 f [ i ] [ i ] f[i][i] f[i][i]表示合并1堆无效状态也应初始化为 0 0 0。
除此之外由于可以随意指定第一颗珠子然后按顺时针方向确定其他珠子的顺序也就是说可以从任何一点出发进行合并。因此需要采用拆环为链的方式进行处理最后求以任意起点开始求释放能量的最大值。
时间复杂度
状态数为 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 210;
int f[N][N];
//s[i]表示第i颗珠子的头标记r[i]表示尾标记
int s[N], r[N];
int main()
{int n;cin n;for(int i 1; i n; i ) {cin s[i];s[i n] s[i]; //拆环为链}//处理尾标记for(int i 1; i 2 * n; i ) r[i] s[i 1];//枚举聚合长度for(int len 2; len n; len ){//枚举聚合起点for(int i 1; i len - 1 n * 2; i ){int j i len - 1; //聚合的结束位置//枚举聚合位置for(int k i; k j; k )f[i][j] max(f[i][j], f[i][k] f[k 1][j] s[i] * s[k 1] * r[j]);}}//求以任一点为起点的最大值int ans 0;for(int i 1; i n; i )ans max(ans, f[i][i n - 1]);cout ans;return 0;
}
