能量项链——noip06提高解题报告

2008 9.7 Sun
日	一	二	三	四	五	六
	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
«月»	2008 - 9	«年»

日志文章

2007年08月23日 22:15:20

能量项链(ruiqi)

本题是一道很经典的dp题目，其实质就是“石子合并问题”的变形，有谈不上什么变形，倒不如说复制更好一点。我想很多的牛人在这个题目失分的原因多为没弄懂题目的意思就下手做了，把题目看简单了。
简单的说：给你一项链，项链上有n颗珠子。相邻的两颗珠子可以合并(两个合并成一个)。合并的同时会放出一定的能量。不同的珠子的合并所释放的能量是不同的。问：按照怎样的次序合并才能使释放的能量最多？
　　我们用top表示第i颗珠子的头标记，用wei表示第i颗珠子的尾标记，合并两颗相邻珠子所释放的能量是：

　　Q=top*wei*wei[i+1]或top*top[i+1]*wei[i+1]; （一个样的）

　　合并不一定按顺序的，本题所提供的样例也是导致出错的一大原因。
　　n个珠子进行一次合并的后，就归结到了n-1个珠子的合并的问题。所以我们想到了动态规划。
　　既然是dp题目，必然要满足dp的两大条件：、
　　1.最优子结构性质；

　　设Q[i,j]表示第i颗珠子到第j颗珠子合并所产生的能量。显然Q[1,n]表示的是合并产生的总的能量。给定一种标号方法，maxQ[1,n]就是所要求的。设最后一次合并在k处进行，则有Q[1,n]＝Q[1,k]＋Q[k+1,n]＋top[1]*wei[k]*wei[n]。要Q[1,n]最大，必然要Q[1,k]，Q[k+1,n]最大。

　　证明：假设Q[1,k]不是最大，则必然存在一Q'[1,k]>Q[1,k]。那么就有Q'[1,n]＝Q'[1,k]＋Q[k+1,n]＋top[1]*wei[k]*wei[n]>Q[1,k]。这与Q[1,n]的最优性矛盾。

　　最优子结构性质得证。

2.无后效性；

　　无后效性是显然的，进行某次合并，合并前与合并后状态是相对独立，不相关联，互不影响的。

　　算法已经定了下来了，关键是怎么实现了。

　　项链是一个环，而我们处理是对一个串进行的。所以我们要把项链从某处割断展开，不同处的割断对应着不同的展开方法，也就是对应着不同的标号方法。产生的maxQ[1,n]也就不同的。所以我们要对这些maxQ[1,n]进行打擂，取其最大的一个，即为解了。

dp的转移方程是：

Best=maxQ[1,n] 1<=i<=n (i表示从第i颗珠子处展开，顺次标号）；

Q[i,j]=max{Q[i,k]+Q[k+1,j]+top*wei[k]*wei[j] 1<=i<=k<j<=n };

其中Q[i,i]=0 1<=i<=n;

dp的时间复杂度为O(n^3)，n种的展开方法对应需要n次的dp，所以时间复杂度为O(n^4)。空间为O(n^2)。

显然O(n^4)过这个题目是有点欠缺的，对的大的数据貌似很容易超时的。

　　如果仔细想想，我们还是做了很不重复的工作的，不同的展开方式中必然存在着很多的大量的重复运算。于是还有很大的优化空间，既然展开做了很多的重复的工作，那么就合并起来吧。回到起点，开始的时候为什么我们要对项链做n次的展开呢，基于我们在运算的时候不能够实现第一颗珠子与第n颗珠子的相邻性。为了一次dp就实现所以的的珠子的相邻性，我们做如下处理：

a[1],a[2],a[3]...a[n],a[1],a[2]...a[n-1]　

（原来的）　（延伸的）

　　有就是：

a[1],a[2],a[3]...a[n],a[n+1],a[n+2]...a[m]　　　

　　显然m=2n-1;

　我们对这一串珠子dp一次即可得解；dp方程为：

　　　Best=max{Q[i,i+n-1] 1<=i<=n}

Q[i,j]=max{Q[i,k]+Q[k+1,j]+top*wei[k]*wei[j] 1<=i<=k<j<=min(i+n-1,m)}

其中Q[i,i]=0 1<=i<=m;

显然时间复杂度为O(n^3)，空间为O(n^2)。min(i+n-1,m)已经对dp进行了优化。

到这里我们可以很完美的过这个题目的所以数据了；但还是觉得不够快，想用四边形优化，但想了想显然是不可以的，W函数不是单调的。

用堆的知识可以更多的优化为（O(n^2*log₂n)）。这里就不多说了，写起来挺烦的。

附程序：
program Qi(inout,output);
var
n,m:integer;
top,wei:array[1..200] of integer;
f:array[1..200,1..200] of longint;
procedure init;
var
i:integer;
begin
readln(n);
for i:=1 to n do read(top);
readln;
for i:=1 to n-1 do wei:=top[i+1];
wei[n]:=top[1];
m:=n*2-1;
for i:=n+1 to m do begin top:=top[i-n]; wei:=wei[i-n]; end;
end;
procedure doit;
var
p,i,j,k:integer;
begin
fillchar(f,sizeof(f),0);
for p:=1 to n-1 do
for i:=1 to m-1 do
begin
j:=i+p;
if j>m then break;
for k:=i to j-1 do
if f[i,j]<f[i,k]+f[k+1,j]+top*wei[k]*wei[j]
then f[i,j]:=f[i,k]+f[k+1,j]+top*wei[k]*wei[j]
end;
end;
procedure print;
var
i:integer; best:longint;
begin
best:=0;
for i:=1 to n do
if best<f[i,i+n-1] then best:=f[i,i+n-1];
writeln(best);
end;
begin
init;
doit;
print;
end.

ruiqi说：谢谢牛们的支持！

附件：

能量项链.rar (6 K)

Tags：能量项链

类别：原创解题报告 | 评论(2) | 浏览(1381) | 收藏

2楼 [匿名]ruiqi 2008年03月20日 11:51:48 Says:

snooy~~~很久以前的了~~当时我不会C您到网上搜索一下应该回有的~~

1楼 [匿名]xilin 2008年03月10日 19:03:17 Says:

可不可以有c语言的程序？
看不懂…………

ruiqi 的小小sky

日历

日志分类

存　档

文章搜索

日志文章