为什么只有50分？不是标号字典序最小吗？
#include<iostream>
using namespace std;
int n;
int MAX;
int a[10011];
int f[10011];
int p[10011];
int ans[10011],l;
int main()
{
freopen("maxxl.in","r",stdin);
freopen("maxxl.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
MAX=-1; int k;
for(int i=1;i<=n;++i){
f[i]=1; p[i]=i;
for(int j=1;j<=i-1;++j)
if(a[i]>a[j]&&f[i]<f[j]+1){
f[i]=f[j]+1;
p[i]=j;
}
if(f[i]>MAX){
MAX=f[i];
k=i;
}
}
printf("%d\n",MAX);
l=0;
while(k!=p[k]){
ans[++l]=a[k];
k=p[k];
}
ans[++l]=a[k];
for(int i=MAX;i>1;--i)
printf("%d ",ans[i]);
printf("%d\n",ans[1]);
return 0;
}

后缀数组真是强悍啊!

ST算法适合数据个数不是特别多，但是查询很多。线段树时候数据多，但是查询少。

终于过了这个题了 哈哈哈

费用流，或者KM

经过n次的提交，终于通过了

dijkstra

。。。

并差集真简单

Treap万岁

Pascal C C++
用户 运行时间 详细记录
用户 运行时间 详细记录
feyu 0.463 查看
用户 运行时间 详细记录
zqzas 0.462 查看
CmYkRgB123 0.477 查看

POI1997的题，好像还是山东的省选

的确啊，数据太弱了，丝毫不能体现出我的动态规划的优越性

明明是树，搜索就行了，不用最短路。。。。。

这一题数据比较大～Dijkstra，Floyd来求多源都是O(n^3)的……不行～
因为是一个树，有n-1条边，所以要用SPFA，存储图要用邻接表，这样求单源的是O(kE)，此题球多源就是n倍的O(kE)，因为E=n-1，所以综合下来是n^2的～这样才可以通过～

虽然题目只是要求对于“最大获利”输出最靠前的方案。
但是，事实上，由于问题背景是“商人”，那么对于可能的利润为0甚至为负的单种物品购买情况都是不应当考虑的。
[upatat]俄，利润为负的情况是我考虑不周，不可能出现。上面的“甚至为负”请无视。

发了四次才通过,原来是当位满十忘记进位了。我的是麻烦算法，就不发了。

已更正

好世道～～～～

庆祝一下，终于写对Treap查找前驱后继了。