SGU 304 — Mars Stomatology
题目描述看这段聊天记录:
Killa.sqybi 22:29:21
就是说…两排点
Killa.sqybi 22:29:38
左边那排每个点都有一条边连向右边那排的某个点
Killa.sqybi 22:29:45
然后每个点有一些权值
Killa.sqybi 22:30:05
选取一些边
Killa.sqybi 22:30:15
然后这些边上的点组成一个集合
Killa.sqybi 22:30:38
要求这个集合的权值之和不能超过P
Killa.sqybi 22:30:45
问最多选取几个左边的点
看起来很简单的题啊…我刚开始想用网络流,结果问MaShuo,他说是DP…然后我就突然想到怎么做了…
Killa.sqybi 23:39:14
首先啊..把所有左边的点按照连到右边点的顺序重新排序
Killa.sqybi 23:39:55
然后d[i,j]表示排序后左边前i个点选j个的最小花费
Killa.sqybi 23:39:57
和p比一下..
实现上还有一些小的注意事项,比如有的右边的点和左边的任意一个点没有连边,所以f()里面处理i=j的情况要注意.
WA on 1,8,10,11,11…第六次submit,AC了…
{
SGU 304; Mars Stomatology
- sqybi’s code
- DP
}
//for my winsty
program sgu304_sqybi;
const
nn = 600;
mm = 600;
var
n, m, p, i, j, t, ans, ansx, edgeNum, x, y, temp: longint;
a, c, r, next, adj, adjr: array[1..nn]of longint;
b, head: array[1..mm]of longint;
d: array[1..nn, 1..nn]of longint;
dt: array[1..nn, 1..nn]of longint;
procedure addEdge(x, y, z: longint);
begin
inc(edgeNum);
adj[edgeNum] := y;
adjr[edgeNum] := z;
next[edgeNum] := head[x];
head[x] := edgeNum;
end;
procedure f(i, j: longint);
var
k: longint;
begin
if i = j then begin
d[i, j] := 0;
for k:=1 to i do
d[i, j] := d[i, j] + a[k];
for k:=1 to c[i] do
if head[k] <> 0 then
d[i, j] := d[i, j] + b[k];
exit;
end;
if j = 1 then begin
d[i, j] := a[i] + b[c[i]];
exit;
end;
d[i, j] := maxlongint;
for k:=j-1 to i-1 do begin
if d[k, j-1] = -1 then f(k, j-1);
t := d[k, j-1] + a[i];
if c[k] <> c[i] then
t := t + b[c[i]];
if t < d[i, j] then begin
d[i, j] := t;
dt[i, j] := k;
end;
end;
end;
procedure print(i, j: longint);
var
k: longint;
begin
if i = j then begin
for k:=1 to i do write(r[k], ‘ ‘);
exit;
end;
if j = 1 then begin
write(r[i], ‘ ‘);
exit;
end;
print(dt[i, j], j-1);
write(r[i], ‘ ‘);
end;
begin
readln(n, m, p);
for i:=1 to m do read(b[i]);
readln;
for i:=1 to n do begin
readln(x, y);
addEdge(y, x, i);
end;
t := 0;
for i:=1 to m do begin
temp := head[i];
while temp <> 0 do begin
inc(t);
a[t] := adj[temp];
r[t] := adjr[temp];
c[t] := i;
temp := next[temp];
end;
end;
fillchar(d, sizeof(d), $FF);
ans := 0;
for i:=n downto 1 do begin
for j:=n downto i do begin
if d[j, i] = -1 then f(j, i); //d[x, y]:在前x个里选y个(x选)的最小花费
if d[j, i] <= p then begin
ans := i;
ansx := j;
break;
end;
end;
if ans <> 0 then break;
end;
writeln(ans);
if ans <> 0 then
print(ansx, ans);
writeln;
end.
阅读(116 次)