作者Lucemia (生の直感、死の予感)
看板Prob_Solve
标题Re: [讨论] GCJ结束了我要伸解法～
时间Wed Jul 30 21:42:39 2008
: 3a:greedy
: 最小的尽量全部塞一起。
: 目前还没想到怎样证orz...
: 时间复杂度：O(n lg n) (sorting)
这题和 1a 一模一样
也可以看成是两列元素要进行向量相乘 求最小
证明也一样
: 3b:Divide and conquer and remember used stated (DP)
: 我们只在意余数，所以其实在一个{1 .. 2*3*5*7}的ring就足以
: model我们看到的所有数字。
: State有strlen*2*3*5*7个，因为断一次数字，後面要什麽数字，
: 只跟前面分别对2,3,5,7的余数有关，跟真正加减起来的数字无关。
: 然後就对数字的每个数字之间都断断看，每次断都加减看看就好。
: 时间复杂度： O(n) 因为2,3,5,7是constant.
: 3c.
: 不会....
我猜应该也是dp, 还没时间写code实验
state(i,j) 定为，第一项为i, 最後项为j的递增数列数
假设 j < i => state(i,j) = 0
假设 i < j =>
sum( state(i,k) * state(k,j) | 对於所有 k 介於i,j间 且满足 i<k<j)
所有可能数则为 sum(state(i,j) for all i,j)
大概是这样 也可能有问题
烦请指正了。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.113.88.50
1F：推 ledia:最後这题意思是 O(n^3) 吗? 07/31 01:12
2F：→ Lucemia:实际做了发现 这题很明显不是要考dp的, N太大了 08/01 00:44
3F：→ Lucemia:从後面开始算 累计排列组合数就好 08/01 00:45
4F：推 Arton0306:这一题要O(NlogN)大测资才会过 08/01 19:19
5F：→ scan33scan33:用segment tree建dp的内表? 08/03 04:15
6F：→ Lucemia:对 要透过 segment tree 来记 08/03 04:18
7F：→ Lucemia:GCJ Group 上有人提供 bit indexed tree 的解法 很漂亮 08/03 04:19