Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Re:这个题可以用dp做（前提是下属猜想成立），见内

Posted by dugushuiyi at 2008-07-03 15:55:58 on Problem 2313 and last updated at 2008-07-03 15:56:55
In Reply To:这个题可以用dp做（前提是下属猜想成立），见内 Posted by:dugushuiyi at 2008-07-03 15:51:23

猜想：
存在一个最有解满足：Bi属于A对于任意i成立。

dp方法：
d(i,j)表示已确定前i个B的值，Bi的值为Aj。
则状态表示O（n^2），状态转移O（n）。
如果使用数据结构，状态转移可以优化到o(1)

Followed by:

Post your reply here: