描述
在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为（Mars单位），新产生的珠子的头标记为m，尾标记为n。
需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。
例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：
(4⊕1)=10*2*3=60。
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为
((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。
格式
输入格式
输入文件的第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当1≤i＜N时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。
至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。
输出格式
输出文件只有一行，是一个正整数E（E≤2.1*109），为一个最优聚合顺序所释放的总能量。
样例1
样例输入1[复制]
42 3 5 10
样例输出1[复制]
710
限制
1s
来源
NOIP2006第一题
题目类型：区间DP+环形
算法分析：将环通过倍增变成一个序列，然后在序列上进行区间DP，形式类似于矩阵乘法的过程。注意最后取最大值的时候要将dp[i][i+n-1]中的所有值都枚举一遍才能得到结果!!!
|
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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; const int INF = 0x7FFFFFFF; const int MOD = 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1000 + 66; struct Node { int h, e; }; Node a[maxn]; int b[maxn], dp[maxn][maxn]; int main() { // ifstream cin ("aaa.txt"); int n; cin >> n; for (int i = 1; i <= n; i++) cin>> b[i]; for (int i = 1; i <= n; i++) { if (i == n) { a[i].h = b[i]; a[i].e = b[1]; } else { a[i].h = b[i]; a[i].e = b[i+1]; } } for (int i = n + 1; i <= 2 * n; i++) { a[i].h = a[i-n].h; a[i].e = a[i-n].e; } // for (int i = 1; i <= 2 * n; i++) // cout << a[i].h << " " << a[i].e << endl; memset (dp, 0, sizeof (dp)); for (int i = 2; i <= 2 * n; i++) { for (int j = 1; j + i - 1 <= 2 * n; j++) { for (int k = j; k < j + i - 1; k++) dp[j][j+i-1] = max (dp[j][j+i-1], dp[j][k] + dp[k+1][j+i-1] + a[j].h * a[k].e * a[j+i-1].e); } } int maxval = -INF; for (int i = 1; i <= n; i++) maxval = max (maxval, dp[i][i+n-1]); cout << maxval << endl; return 0; } |
- « 上一篇：vijos1165
- vijos1448：下一篇 »