Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

这题该怎么做啊?我用dp,WA了...

Posted by Jet407 at 2005-05-07 20:44:54 on Problem 2168
{\$q-,r-,s-}
const
maxn=1002;
var
n,m,max,ms,mi:integer;
a,b,bel,ind:array[1..maxn]of integer;
G:array[1..maxn,0..maxn]of integer;
mk,f,st:array[0..maxn,0..maxn]of integer;
ls:array[1..maxn,0..3]of integer;
sel:array[1..maxn]of boolean;
procedure swap(var a,b:integer);
var
c:integer;
begin
c:=a;a:=b;b:=c;
end;
procedure sort(p,q:integer);
var
i,j,mid:integer;
begin
i:=p;j:=q;
mid:=ind[p+random(q-p+1)];
repeat
while ls[ind[i]][0]<ls[mid][0] do inc(i);
while ls[ind[j]][0]>ls[mid][0] do dec(j);
if i<=j then
begin
if i<j then swap(ind[i],ind[j]);
inc(i);
dec(j);
end;
until i>j;
if i<q then sort(i,q);
if j>p then sort(p,j);
end;
var
i:integer;
begin
fillchar(mk,sizeof(mk),0);
m:=0;
for i:=1 to n do
begin
if mk[a[i],b[i]]>0 then
begin
bel[i]:=mk[a[i],b[i]];
inc(ls[mk[a[i],b[i]]][3]);
end else
begin
inc(m);
bel[i]:=m;
ls[m][0]:=a[i];
ls[m][1]:=b[i];
ls[m][2]:=n-a[i]-b[i];
ls[m][3]:=1;
mk[a[i],b[i]]:=m;
ind[m]:=m;
end;
end;
sort(1,m);
end;
procedure print;
var
s,i,j:integer;
begin
s:=ms;
i:=mi;
fillchar(sel,sizeof(sel),0);
while i>0 do
begin
sel[i]:=true;
j:=i;
i:=st[s,i];
dec(s,ls[j][2]);
end;
write(n-max);
for i:=1 to n do
if not sel[bel[i]] then
write(' ',i);
writeln;
end;
procedure main;
var
s,i,j,x,y:integer;
begin
for x:=1 to m do
begin
i:=ind[x];
G[i,0]:=0;
if ls[i][2]<=0 then continue;
for y:=succ(x) to m do
begin
j:=ind[y];
if ls[j][2]<=0 then continue;
if (ls[i][0]+ls[i][2]<=ls[j][0])and(ls[i][1]>=ls[j][1]+ls[j][2])and(ls[i][2]+ls[j][2]<=n) then
begin
inc(G[i,0]);
G[i,G[i,0]]:=j;
end;
end;
end;
fillchar(f,sizeof(f),\$FF);
for x:=1 to m do
begin
i:=ind[x];
if ls[i][2]>0 then
begin
f[ls[i][2],i]:=ls[i][3];
st[ls[i][2],i]:=0;
end;
end;
for s:=1 to n-1 do
for x:=1 to m do
begin
i:=ind[x];
if (f[s][i]>-1) then
begin
for y:=1 to G[i,0] do
begin
j:=G[i,y];
if (s+ls[j][2]<=n)and(f[s,i]+ls[j][3]>f[s+ls[j][2],j]) then
begin
f[s+ls[j][2],j]:=f[s,i]+ls[j][3];
st[s+ls[j][2],j]:=i;
end;
end;
end;
end;
ms:=0;
mi:=0;
max:=0;
for s:=1 to n do
for i:=1 to m do
if f[s][i]>max then
begin
max:=f[s][i];
ms:=s;
mi:=i;
end;
print;
end;
begin
while not seekeof do
begin
main;
end;
end.

Followed by: