> 优化芝麻优化过了，虽然知道优化状态转移的话可以把转移蛋疼到接近O(1)，但是还是想练习一下难度比较大的优化：
> 
> 我用的是上下界估价函数，然后剪枝：  用这个方法配合状态转移优化说不定能搞N<=10^5数据量，改天再搞，不知道  原始数据的题目哪个OJ有。。。。

随机测了几组N==1000的数据，有用的状态数从 10^6优化到了 17万左右，不知道N==10^5效果怎么样。。。。

• 不知道唉，我没有测试数据，只有PDF (67) yygy 2014-07-25 08:36:39
  • 测试数据可以下载。 (0) yygy 2014-07-25 08:38:28
    • Re:测试数据可以下载。 (73) yygy 2014-07-25 08:39:12
      • Re:测试数据可以下载。 (13) yygy 2014-07-25 10:05:23
        • 正解是什么？ (15) yygy 2014-07-25 10:13:15
          • 看了后面几个大数据，里面尽然 有一些答案是i don't know (0) yygy 2014-07-25 10:22:23
            • Re:看了后面几个大数据，里面尽然 有一些答案是i don't know (60) tasty 2014-07-25 12:43:45
              • 对于10000的数据要跑103.524000S (68) yygy 2014-07-25 14:28:11
                • N^2的状态表示不可能通过10万的数据吧。内存也开不了。必须降维啊，难道是二分加判断吗。 (0) yygy 2014-07-25 14:29:09
                  • Re:N^2的状态表示不可能通过10万的数据吧。内存也开不了。必须降维啊，难道是二分加判断吗。 (153) tasty 2014-07-25 14:34:49
                    • 你的状态表示是怎么样的啊？看了你的代码，好奇怪的状态表示，三维的，前面还带个3. (0) yygy 2014-07-25 14:37:04
                      • Re:你的状态表示是怎么样的啊？看了你的代码，好奇怪的状态表示，三维的，前面还带个3. (47) tasty 2014-07-25 14:40:39
                        • Re:你的状态表示是怎么样的啊？看了你的代码，好奇怪的状态表示，三维的，前面还带个3. (204) tasty 2014-07-25 14:43:02
                          • 你跑1万的数据用了多少时间？这n^3再怎么降也不可能把10万的数据稿出来吧。 (165) yygy 2014-07-25 15:02:26
                            • Re:你跑1万的数据用了多少时间？这n^3再怎么降也不可能把10万的数据稿出来吧。 (627) tasty 2014-07-25 15:16:31