导弹拦截(NOIP1999)

deadrain 发表于 2007-08-16 23:19:02

题目略有改动,第一问即求最长下降子序列,第二问求最长升序子序列,要减1!

CODE:
-------------------------------------

program p1303;
var
 s:string;
 c:char;
 a:array[1..20] of integer;
 f:array[1..20] of longint;
 n,i,j,k:integer;
begin
 n:=0;s:='';
 while not eoln do
 begin
  read(c);
  if c=',' then
  begin
   inc(n);
   val(s,a[n],k);
   s:='';
  end
  else s:=s+c;
 end;
 inc(n);
 val(s,a[n],k);

 fillchar(f,sizeof(f),0);
 k:=1;f[n]:=1;
 for i:=n-1 downto 1 do
 begin
  f[i]:=1;
  for j:=i+1 to n do
   if (a[i]>a[j]) and (f[i]<f[j]+1) then f[i]:=f[j]+1;
  if f[i]>k then k:=f[i];
 end;
 write(k,',');

 fillchar(f,sizeof(f),0);
 k:=1;f[1]:=1;
 for i:=2 to n do
 begin
  f[i]:=1;
  for j:=i-1 downto 1 do
   if (a[j]<a[i]) and (f[i]<f[j]+1) then f[i]:=f[j]+1;
  if f[i]>k then k:=f[i];
 end;
 write(k-1);
end.

关键词(Tag): noip vijos


收藏: QQ书签 del.icio.us 订阅: Google 抓虾

最新评论


  • 123456798
    2008-01-28 17:41:19 匿名 218.202.*.*

发表评论

* 昵称

已经注册过? 请登录

新用户请先注册 以便能显示头像及追踪评论回复

Email
网址
* 评论
表情
 
 

分类小组论坛
杂谈, 娱乐、八卦, 文学、艺术, 体育, 旅游、同城, 象牙塔, 情感, 时尚、生活, 星座, 科技

请注意遵守中华人民共和国法律法规, 如威胁到本站生存, 将依法向有关部门报告, 同时本站的相关记录可能成为对您不利的证据.

相关法律法规
全国人大常委会关于维护互联网安全的决定
中华人民共和国计算机信息系统安全保护条例
中华人民共和国计算机信息网络国际联网管理暂行规定
计算机信息网络国际联网安全保护管理办法
计算机信息系统国际联网保密管理规定