引用gemini_1：

这一题理论上说dp+贪心是不对的，例如

4 5 6 7 8 14 15 16 1 2 3 9 10 11 12 13

若贪心：4 5 6 7 8 9 10 11 12 13

　　 14 15 16

　　 1 2 3

　　 要三组

实际上：4 5 6 7 8 14 15 16

　　 1 2 3 9 10 11 12 13

　　 只要两组

至少要再添加!!!

我的ac率啊……

这题最长子序列,重复多次DP,直到子序列为0还是dp+贪心都是错的，这是数据弱而已。

某年的noip提高组。。

dismory的应该是对的

水题！！！一次AC!

编译通过...

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

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

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

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

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

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

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

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

var

i,j,k,step,step1,step2,lens,size,jilu,temp,score,answer,answer1,answer2:longint;

q,a,ai,s:array[0..100]of longint;

b:array[0..50]of boolean;

st:ansistring;

flag:boolean;

ans:array[0..50]of longint;

//======================================

procedure init;

begin

readln(st);

step:=0;

answer1:=-1;

fillchar(b,sizeof(b),true);

step1:=1;

lens:=length(st);

for i:=1 to lens do

if st[i]=','

then begin

inc(step);

val(copy(st,step1,i-step1),temp);

a[step]:=temp;

step1:=i+1;

end;

inc(step);

val(copy(st,step1,i-step),temp);

a[step]:=temp;

jilu:=0;

flag:=false;

step1:=0;

end;

//======================================

procedure solve;

begin

s[0]:=0;

answer2:=0;

for i:=1 to step do

begin

s[i]:=0;

for k:=0 to i-1 do

if b[i] and b[k] then

if ((k=0)or(a[k]>a[i]))and(s[k]+1>s[i])

then begin

s[i]:=s[k]+1;

ans[i]:=k;

end;

end;

for i:=1 to step do

if (s[i]>answer2)

then begin

answer2:=s[i];

k:=i;

end;

size:=0;

inc(answer1);

repeat

inc(size);

q:=k;

k:=ans[k];

until k=0;

for i:=1 to size do

b[q[i]]:=false;

for i:=1 to step do

jilu:=jilu+ord(b[i]);

if jilu=0

then begin

flag:=true;

exit;

end;

end;

//======================================

procedure solve1;

begin

s[0]:=0;

answer:=0;

for i:=1 to step do

begin

s[i]:=0;

for k:=0 to i-1 do

if b[i] and b[k] then

if ((k=0)or(a[k]>a[i]))and(s[k]+1>s[i])

then begin

s[i]:=s[k]+1;

ans[i]:=k;

end;

end;

for i:=1 to step do

if (s[i]>answer)

then begin

answer:=s[i];

k:=i;

end;

size:=0;

inc(answer1);

repeat

inc(size);

q:=k;

k:=ans[k];

until k=0;

for i:=1 to size do

b[q[i]]:=false;

jilu:=0;

for i:=1 to step do

jilu:=jilu+ord(b[i]);

if jilu=0

then begin

flag:=true;

exit;

end;

end;

//======================================

begin

init;

solve;

if flag

then begin

writeln(answer2,',',answer1);

halt;

end;

repeat

fillchar(ans,sizeof(ans),0);

solve1;

until (flag)or(step=0);

writeln(answer2,',',answer1);

end.

题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题

题题题题题题题题题题题题题题题题题题题题题题题题题题题题水水水水题题题题题

题题题题题题题题题题题题题题题题题题题题题题题题水水水水水水水水水题题题题

题题题题题题题题题题题题题题题题题题水水水水水水水水水水水水水水水题题题题

题题题题题题题题题题题题题题题题水水水水水水水水水水水水水水水题题题题题题

题题题题题题题题题题题水水水水题水水水水水水水水水水水题题题题题半题题题题

题题题题题题题题水水水水水水水题水水水题题水水水水水题题题题题题题题题题题

题题题水水水水水水水水水水水水题题题题题题水水水水题题题题题题题题题题题题

题水水水水水水水水水水水水水水题题题题题题水水水水题题题题题题题题题题题题

题水水水水水水水水水水水水题题题题题题题水水水水水水水水水水水题题题题题题

题水水水水水水水水水水水水题题题题题题水水水水水水水水水水水水水水题题题题

题题水水水水水水水水水水题题题题题水水水水水水题题题水水水水水水水题题题题

题题题题题题题题水水水水题题题题题水水水水题题题题题题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水水题题水水题题题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水水题题水水水水题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水水题题水水水水题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水水题题水水水题题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水水题题水水水题题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水水题水水水水题题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水水题水水水水题题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水水题水水水水题题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水水题水水水水题题水水水水水题题题题题

题题题题题题题题水水水水题题题题水水水题题水水水水题题水水水水水题题题题题

题题水水题题题水水水水水题题题题水水水题题水水水题题题水水水水水题题题题题

题题水水水水水水水水水水题题题题题水水题题水水题题题题水水水水水题题题题题

题题题水水水水水水水水水题题题题题题题题水水水题题题题水水水水题题题题题题

题题题题题水水水水水水水题题题题题题题题水水水题水水水水题题题题题题题题题

题题题题题题水水水水水水题题题题题题题水水水水题题水水水水题题题题题题题题

题题题题题题题题题水水水题题题题题题水水水水水题题题水水水水水水水题题题题

题题题题题题题题题题题题题题题题水水水水水水题题题题题水水水水水水题题题题

题题题题题题题题题题题题题题题水水水水水水题题题题题题水水水水水水水题题题

题题题题题题题题题题题题题题水水水水水题题题题题题题题题水水水水水水题题题

题题题题题题题题题题题题题水水水水水题题题题题题题题题题题水水水水题题题题

题题题题题题题题题题题题水水水题题题题题题题题题题题题题题题水水水题题题题

题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题

注意输出是writeln(ans,',',sys-1)

而不是writeln(ans);

writeln(sys-1);

害我刮了一次!!!

LDS+LIS

动规+贪心

最长子序列,重复多次DP,直到子序列为0.

编译通过...

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

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

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

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

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

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

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

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

算法：DP+Binary_serach

解析：维护一个数组h[i]，记录下长度为i的不升序列的结尾导弹的高度，对于每个导弹j，f[j]=max{i|h[i]>=a[j]}+1,显然h是单调的，所有可以使用Binary_search来查找，还有就是h[i]中总是存i长度的不升序列结尾导弹最高的那个高度，有更高的则更新。

终于对了。。。。。

编译通过...

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

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

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

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

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

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

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

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

这道题真是麻烦! 害我提交了N次 大家一定要注意啊!!!

我输入都搞了半天

最后一个测试数据太刁钻了!!! - -!

郁闷ing

编译通过...

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

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

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

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

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

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

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

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

采用N次lis的办法，但我觉得这样算第2问一定是错的

但是AC了就好……

基本功一定要扎实啊。。。晕菜，我交了三次才过。

编译通过...

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

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

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

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

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

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

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

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

编译通过...

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

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

├ 测试数据 03：答案错误...

　├ Hint: 注意考虑边界情况　├ 标准行输出

　├ 错误行输出

├ 测试数据 04：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

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

Unaccepted 有效得分：66 有效耗时：0ms

边界情况是什么? 哪位高手能提示一下　　不甚感激！！！

编译通过...

├ 测试数据 01：答案错误...

　├ Hint: 注意观察样例数据　

├ 标准行输出 5,1

　├ 错误行输出 5,2

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

├ 测试数据 03：答案错误...

　├ Hint: 注意考虑边界情况　

├ 标准行输出 7,3

　├ 错误行输出 7,4

├ 测试数据 04：答案错误...　

├ 标准行输出 5,7

　├ 错误行输出 5,8

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

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

我....我 .到底是为什么啊,那个"注意样例""考虑边界"是什么意思

哪位高手知道啊

给个数据也行,我自己再去研究下

谢谢了 ...........................................

DP+贪心=Accepted

最后答案全部都要减1，好晕哦。···！！！！！！！！

我把开的两个数组用混了，居然过了3个点！

二分降复杂度。。。