160 条题解
-
0
1898098 LV 3 @ 2007-10-23 11:20:19
考试时以为是贪心……
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
ljj5112898 LV 3 @ 2007-10-20 09:10:54
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
下面贴程序的人很多，我就不贴了... -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
比赛时用贪心。。过了三组。。。。。T。T -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
这条题真的挺经典的...
与矩阵链相乘相似..{与P1038..添加括号类似}..DP的状态转移方程也差不多..
不过这条题的一个技巧在于..把数组扩大两倍...把数据copy一次放在后面..这样就可以避免项链环形所带来的麻烦...枚举完所有情况..且不用搞到头晕晕的..{与某一题..石子合并..相似..都是要把环化为线性的..}
但以这条题的数据..本来矩阵链相乘是O(N)^3的时间复杂度的.再加上枚举环从哪里断开..一共是O(N)^4..应该比较勉强且很大几率会超..但是结果AC掉了..{听人家说vijos的评测机比较仁慈..今日一见..果然如此..}
-
0
LV 0 @ 2007-07-25 10:30:20
奇怪为什么n^4也行。
-
0
根本就是从合并石子的原题上copy过来的。
此题的动态转移方程同合并石子的基本一样，唯一的不同即是：
在动态转移方程
cost[i][j]=max{cost[i][k]+cost[(i+k-1) mod n+1][j-k]}+data[i][j]
中，要把 data[i][j] 改成 num[i]*num[(i+k-1) mod n+1]*num[(i+j-1) mod n+1] (其中num[i]数组从左到右一字形摆放时编号为i的数字的头标记）。
数据范围是100，O(n^3)都绰绰有余，不需要四边形不等式的优化变成O(n^2)也可以过。 -
0
LatiosWang LV 6 @ 2007-07-08 11:16:24
for i:=2*n downto 1 do
for j:=i+2 to 2*n do
if j-i>n then break
else
for k:=i+1 to j-1 do
if f -
0
ZhouYuChen LV 5 @ 2007-06-25 13:25:19
矩阵链相乘问题
1898098
LV 3
@ 2007-10-23 11:20:19
