题目描述啊

出题人题目描述不厚道

RP--

郁闷，第一次，90，一模一样的程序，第二次95，第三次AC

真是郁闷死了

看来要学学nlogn的longestup的算法了，O(n^2)很容易超时啊！！！

第一次交：

编译通过...

├ 测试数据 01：答案正确... 822ms

├ 测试数据 02：答案正确... 853ms

├ 测试数据 03：答案正确... 838ms

├ 测试数据 04：答案正确... 838ms

├ 测试数据 05：运行超时...

├ 测试数据 06：答案正确... 181ms

├ 测试数据 07：答案正确... 166ms

├ 测试数据 08：答案正确... 197ms

├ 测试数据 09：答案正确... 212ms

├ 测试数据 10：答案正确... 181ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：95 有效耗时：4288ms

什么都没改，再交：

编译通过...

├ 测试数据 01：答案正确... 838ms

├ 测试数据 02：答案正确... 822ms

├ 测试数据 03：答案正确... 806ms

├ 测试数据 04：答案正确... 822ms

├ 测试数据 05：答案正确... 822ms

├ 测试数据 06：答案正确... 166ms

├ 测试数据 07：答案正确... 166ms

├ 测试数据 08：答案正确... 134ms

├ 测试数据 09：答案正确... 150ms

├ 测试数据 10：答案正确... 166ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：4892ms

无语。。。。。。

O(nlogn)

用best[i]记录长度为i序列末尾的最小值

易证best数组是不升的，可以二分求解

编译通过...

├ 测试数据 01：答案正确... 697ms

├ 测试数据 02：答案正确... 681ms

├ 测试数据 03：答案正确... 697ms

├ 测试数据 04：答案正确... 712ms

├ 测试数据 05：答案正确... 681ms

├ 测试数据 06：答案正确... 119ms

├ 测试数据 07：答案正确... 119ms

├ 测试数据 08：答案正确... 119ms

├ 测试数据 09：答案正确... 134ms

├ 测试数据 10：答案正确... 119ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：4078ms

事实证明,数据弱,O(N^2)也能过。

LX的题解很详细了 我就不多说了 就是一个由城市联谊变形过来的LongestUp

看到十楼的话。一股智商上的优越感油然而生

看懂题目花了半小时

最后发现是经典问题!!!

O(nlogn);

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

O(N*N)的效果

编译通过...

├ 测试数据 01：答案正确... 822ms

├ 测试数据 02：答案正确... 822ms

├ 测试数据 03：答案正确... 775ms

├ 测试数据 04：答案正确... 822ms

├ 测试数据 05：答案正确... 822ms

├ 测试数据 06：答案正确... 150ms

├ 测试数据 07：答案正确... 166ms

├ 测试数据 08：答案正确... 197ms

├ 测试数据 09：答案正确... 150ms

├ 测试数据 10：答案正确... 166ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：4892ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

终于a了

！

哎,快排打错了,0分

-->[red]temp:=xc;xc:=xc[j,1];xc:=temp;

单调队列的应用

Accepted 有效得分：100 有效耗时：0ms

Flag 　　Accepted

题号 　　P1638

类型(?) 　　其它

通过 　　34人

提交 　　75次

通过率 　　45%

难度 　　0

快排+DP+二分查找=0ms

编译通过...

├ 测试数据 01：答案正确... 775ms

├ 测试数据 02：答案正确... 791ms

├ 测试数据 03：答案正确... 791ms

├ 测试数据 04：答案正确... 775ms

├ 测试数据 05：答案正确... 775ms

├ 测试数据 06：答案正确... 134ms

├ 测试数据 07：答案正确... 166ms

├ 测试数据 08：答案正确... 166ms

├ 测试数据 09：答案正确... 150ms

├ 测试数据 10：答案正确... 166ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：4689ms

惊险AC

sgu原题~

先快排。

再用优化版的最长上升子序列。。。

开个G数组记录F为1，2，3……时关键值最小的。。

I 2 TO N

J 从G数组DOWNTO 1

明白了题意才知道

这题目好水....

要先排序，很简单的dp

program exqjwj;

var n,i,j,k,l,x,y,m1,m2:longint;

b,d:array[1..500001,1..2]of qword;

procedure kp(l,r:longint);

var i,j,mid,k:longint;

begin

i:=l; j:=r; mid:=b[(l+r) div 2,1];

repeat

while bmid do dec(j);

if ij;

if ll) then

begin

l:=d[j,2];

k:=j;

end;

if l>0 then

begin

d:=l+1;

end;

end;

k:=1;

for j:=1 to n do

if d[j,2]>d[k,2] then k:=j;

write(d[k,2]);

readln;

end.

为什么我的程序算出来的答案都比正解大1？

但是有一个数据又会大2……

type

City=record

a,b:longint;

end;

var

F:array[0..100000]of longint;

c:array[0..100000]of City;

n,m,i,j,ans,p,q,mid:longint;

procedure qsort(l,r:longint);

var

i,j,mid:longint;

swap:City;

begin

i:=l;j:=r;mid:=c[(i+j) shr 1].a;

repeat

while c[i].amid do dec(j);

if ij;

if iF[q] then

begin

if q=ans then inc(ans);

F[q+1]:=c[i].b;

end;

if (c[i].b=F[q])and(q=ans) then inc(ans);

if (c[i].bF[p]) then F[q]:=c[i].b;

end;

writeln(ans);

end.

谁帮忙看下 = =