无聊时自己想了个打印解方法 速度当然没楼上的大神们快- -
深夜又无聊于是乎决定在这里水一贴
用动归的时候已经把每个节点的最大路径值算出来了，
在打印解得时候每次只需要选择比较大的路径值就行（忘了咋推的了 占坑以后补）
从(1,1)开始选择下一行的左边(i+1)(j)或者右边(j+1)(j+1)
比如样例每个状态为
86
57 73
39 46 65
18 27 39 32
12 07 13 24 11
选择的顺序应该是86 73 65 39 24
记录选择的点（用个数组），打印数塔中原来的数据
会发现i是逐层递增的，不需要记录
对于j
d[i+1][j+1]>d[i+1][j]或d[i+1][j+1]<d[i+1][j]
第一种情况时需要把j+1来记录 说明选择的是右边的点 记入数组
第二个则j不需要变 选择的是左边的点 记入数组
打印相应的解就行了

int j=1; now[1]=1; //从点（1,1）开始记录

 for(int i=1;i<=n-1;i++){

 if(d[i+1][j+1]>d[i+1][j]) j++;

 now[m++]=j;

}

for(int i=1;i<=n;i++)

 printf("%d ",a[i][now[i]]);

当初一时兴起想到了一个神奇的压缩trie数占用内存空间的方法。假设trie转移的范围是0~255，这种情况下以直接寻址表的形式跳转的话，也就是每个节点开256个儿子。占用空间极大。
神奇的优化方法:每4位看作一个字符，这样每个节点只需要2^4 = 16个儿子，但是相当于字符串长度 *= 2
这样做可以认为: 时间 *= 2;空间 = 2*sqrt(空间)

场主垃圾线段树板子，常数大如狗。

回复 @mikumikumi :
( 排序之后从小的跑一遍优先解决自己子树的就是最优的了
吐槽: 半个下午.... 把5e4看成了5e5...... M了两次

此题制杖

回复 @Go灬Fire :
装的一手好B（滑稽）

回复 @liu_runda :
+1

真心赞一下评测插件，我按字典序倒序输出的。。

论仔细审题的重要性！！！！！！

回复 @Asm.Def :
Orz萌帝，能学CDQ分治

回复 @Fmuckss :
我推出的公式需要除s来求解的上界，于是就挂了三个点

评测机是不是有问题啊。我的程序本地测试无误，交上去是一个W九个E，NOI2003的标程交上去也是WEEEEEEEEE

写了一个效率最坏O(n^2)的单调队列，居然过了，而且速度接近O(n)……

这个高精实在恶心到我了- -。。

居然直接想到的是每次都整个做一遍spfa

VIP 第一道树链剖分留念~ 3遍才AC我的正确率T^T

天哪... stl的常数啊.....