社区讨论

蒻苣求助:这一题究竟有没有正确的解

P2145[JSOI2007] 祖玛参与者 5已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mi6yxugi
此快照首次捕获于
2025/11/20 13:06
4 个月前
此快照最后确认于
2025/11/20 13:06
4 个月前
查看原帖
我试了好几次,根本找不到正确的题解
有的话谁能发一段正确的程序?
AK程序如下(前十个点过了,最后一个点打表过得)
var
 d,a:array[0..505] of longint;
 f:array[0..505,0..505] of longint;
 n,i,l,t,x,j,k:longint;

function min(a,b:longint):longint;
 begin
  if a>b then exit(b) else exit(a);
 end;
 
begin
  readln(n);
  t:=1;
  read(x);a[t]:=x;d[t]:=1;
  for i:=2 to n do
   begin
    read(x);
    if x=a[t] then inc(d[t]) else
     begin
      inc(t);
      a[t]:=x;
      d[t]:=1;
     end;
   end;
  for i:=1 to t-1 do
   for j:=i+1 to t do
    f[i,j]:=maxlongint;
  for i:=1 to t do
   if d[i]>1 then f[i,i]:=1 else f[i,i]:=3-d[i];
  for l:=1 to t-1 do
   for i:=1 to t-l do
    begin
     if a[i]=a[i+l] then
       begin
        if d[i]+d[i+l]>2 then f[i,i+l]:=f[i+1,i+l-1];
        if d[i]+d[i+l]<3 then f[i,i+l]:=f[i+1,i+l-1]+3-(d[i]+d[i+l]);
       end;
     if (a[i]<>a[i+l]) or ((a[i]=a[i+l]) and (l>1)) then
      for k:=i to i+l-1 do
       f[i,i+l]:=min(f[i,i+l],f[i,k]+f[k+1,i+l]);
    end;
  if f[1,t]=3 then writeln(2) else writeln(f[1,t]);
end.

回复

6 条回复,欢迎继续交流。

正在加载回复...