SGU 116 — Index of super-prime
具体题解看这里:
http://www.briefdream.com/sgu-116/
这道题很囧的一点是,我一直不知道背包的一维写法…
其实就是f[i]=min(f[i-a[j]])+1,然后就ok了…囧死了,因为这个MLE了…
改后AC.
{
SGU 116; Index of super-prime
- sqybi’s code
- DP(package)
}
//for my winsty
program sgu116_sqybi;
const
nn = 10000;
inf = 1000000;
var
n, i, j, lp, lsp, outl: longint;
sp, p, outArr: array[1..nn]of longint;
pf: array[1..nn]of boolean;
d, path: array[0..nn]of longint;
procedure qsort(l, r: longint);
var
i, j, d, t: longint;
begin
if l >= r then exit;
i := l;
j := r;
d := outArr[(l+r) div 2];
repeat
while outArr[i] > d do inc(i);
while outArr[j] < d do dec(j);
if i <= j then begin
t := outArr[i];
outArr[i] := outArr[j];
outArr[j] := t;
inc(i);
dec(j);
end;
until i > j;
qsort(l, j);
qsort(i, r);
end;
procedure f(i: longint);
var
j: longint;
begin
if i = 0 then begin
d[i] := 0;
exit;
end;
d[i] := inf;
for j:=1 to lsp do
if sp[j] <= i then begin
if d[i-sp[j]] = -1 then f(i-sp[j]);
if d[i-sp[j]] + 1 < d[i] then begin
d[i] := d[i-sp[j]] + 1;
path[i] := j;
end;
end;
end;
procedure print(i: longint);
begin
if path[i] <> -1 then begin
print(i-sp[path[i]]);
inc(outl);
outArr[outl] := sp[path[i]];
end;
end;
begin
readln(n);
fillchar(pf, sizeof(pf), true);
lp := 0;
for i:=2 to n do
if pf[i] then begin
inc(lp);
p[lp] := i;
for j:=2 to n div i do pf[i*j] := false;
end;
lsp := 0;
for i:=1 to lp do begin
if p[i] > lp then break;
inc(lsp);
sp[lsp] := p[p[i]];
end;
fillchar(d, sizeof(d), $FF);
fillchar(path, sizeof(path), $FF);
f(n);
if d[n] < inf then begin
writeln(d[n]);
print(n);
qsort(1, outl);
for i:=1 to outl do
write(outArr[i], ‘ ‘);
end
else
writeln(0);
end.
阅读(62 次)