Question

工 作(work.pas) pascal

【问题描述】
当前有n（n<=12）个工作，和8个工人。现在每个工作需要占用一个工人的从[a，b]这个区间的时间（一个工人自然不可能在同一个时间做2个不同的工作），且一个工作不一定是所有工人都能够完成的。现在给出每个工作的描述，问是否存在一种安排方案使得所有工作都能完成。
【输入文件】
输出文件有多组数据。第一行一个数tot表示数据的组数，后面紧接tot组数据。 对于每一组数据的第一行有一个整数n，表示工作的数目。后面n行每行描述一个工作。
对于一个工作，a，b，k，h1，h2……hk来描述，表示这个工作需要占用一个工人[a，b]的时间，并且能够完成这个工作的工人只有k个，标号分别是h1，h2……hk。
【输出文件】
输出文件对于每组输入数据，输出一行YES（如果可以安排一种方案使得工作完成）或者是NO（无法安排一种方案）
【样例输入】
2
2
1 1 1 1
2 2 1 1
2
1 2 1 1
2 2 1 1
【样例输出】
YES NO

急求！！！！！！！！！！！！！！！！！！！！！！

Answer 1

搜索,DP,二分图匹配可以做
数据弱建议搜索orDP
状态压缩DP::::
首先将每个事件分离成2个时间点，然后按照时间先后顺序排序。(n个事件,存成2n个时间点)
f[i][j]为一个bool数组，表示当前处理完第i个时间点，j（当前工人空闲状况，范围0~2^8-1）这个状态是否有可能达到
转移：
f[i][j]=f[i-1][j-k]//如果当前第i个事件点是事件开始时间点
f[i][j]=f[i-1][j+k]//如果当前第i个事件点是事件结束时间点
k是能够完成时间点所代表的事件的工人标号状压后的值
最后输出f[2*n][0]即可

追问

能给出程序吗？？ 谢谢

追答

已经写的很清楚啦..初始化f为false,方程也有写起来很快的
这题我觉得压缩难点..别的没什么了

追问

额，给出程序给你满意

追答

........初赛过了再贴。。。吧

追问

恩恩

追答

程序私信给你了.自己测了几组都对,你先看看吧
(..程序贴出来总被吞.....)

Answer 2

var
tot,toth,n:longint;
ok:boolean;
f:array [1..13,0..8] of longint;
a:array [1..13,1..2] of longint;
v:array [1..8,1..1000] of boolean;
procedure init;
var
i,j,k,x:longint;
begin
fillchar(f,sizeof(f),0);
fillchar(v,sizeof(v),true);
readln(n);
for i:=1 to n do
begin
read(a[i,1],a[i,2],k);
for j:=1 to k do
begin
inc(f[i,0]);
read(f[i,f[i,0]]);
end;
readln;
end;
ok:=false;
end;
function free(t,x,y:longint):boolean;
var
i,j:longint;
begin
for i:=x to y do
if v[t,i]=false then exit(false);
exit(true);
end;
procedure dfs(dep:longint);
var
i,j:longint;
begin
for i:=1 to f[dep,0] do
if free(f[dep,i],a[dep,1],a[dep,2]) then
begin
for j:=a[dep,1] to a[dep,2] do
v[f[dep,i],j]:=false;
if dep=n then begin writeln('YES'); ok:=true; exit; end
else dfs(dep+1);
if ok then exit;
for j:=a[dep,1] to a[dep,2] do
v[f[dep,i],j]:=true;
end;
end;
begin
readln(tot);
for toth:=1 to tot do
begin
init;
dfs(1);
if ok=false then writeln('NO');
end;
end.

Answer 3

搜索：
var
tot,toth,n:longint;
ok:boolean;
f:array [1..13,0..8] of longint;
a:array [1..13,1..2] of longint;
v:array [1..8,1..1000] of boolean;
procedure init;
var
i,j,k,x:longint;
begin
fillchar(f,sizeof(f),0);
fillchar(v,sizeof(v),true);
readln(n);
for i:=1 to n do
begin
read(a[i,1],a[i,2],k);
for j:=1 to k do
begin
inc(f[i,0]);
read(f[i,f[i,0]]);
end;
readln;
end;
ok:=false;
end;
function free(t,x,y:longint):boolean;
var
i,j:longint;
begin
for i:=x to y do
if v[t,i]=false then exit(false);
exit(true);
end;
procedure dfs(dep:longint);
var
i,j:longint;
begin
for i:=1 to f[dep,0] do
if free(f[dep,i],a[dep,1],a[dep,2]) then
begin
for j:=a[dep,1] to a[dep,2] do
v[f[dep,i],j]:=false;
if dep=n then begin writeln('YES'); ok:=true; exit; end
else dfs(dep+1);
if ok then exit;
for j:=a[dep,1] to a[dep,2] do
v[f[dep,i],j]:=true;
end;
end;
begin
readln(tot);
for toth:=1 to tot do
begin
init;
dfs(1);
if ok=false then writeln('NO');
end;
end.

Answer 4

折腾人脑筋的东西,做一控制台程序即可解决.