【Nescafé 31】杯NOIP模拟赛
2024-09-21 13:41:57
t1
题意:n*m的棋盘上从(1,1)走到(n,m),只能向下或向右,一些格子有老鼠,每个老鼠互不相同,当处于与老鼠有重边的格子时,视为看见了这只老鼠,求到终点看到最少的不同老鼠数。
分析:DP 由于求得是看到的不同的老鼠数目,不能直接用过河卒做,因为同一个位置的老鼠可能会统计多次,我们还需要增加一维即方向。
f[i,j,0]表示到从上面一个格子走到(i,j)时最少老鼠数,f[i,j,1]表示左边。
f[i,j,0]:=min(f[i-1,j,0]+a[i,j-1],f[i-1,j,1])+a[i+1,j]+a[i,j+1];
f[i,j,1]:=min(f[i,j-1,1]+a[i-1,j],f[i,j-1,0])+a[i+1,j]+a[i,j+1];
对于(i,j)如果左边有老鼠,那么从(i-1,j-1)走到(i-1,j)再到(i,j)会看到该老鼠两次但只能记为1次,(i-2,j)走到(i-1,j)再到(i,j)时只看到该老鼠一次,故要加上这一次。上边有老鼠也同理。
代码:
program mouse;
var
a:array[..,..]of longint;
f:array[..,..,..]of longint;
n,i,m,j:longint;
function min(x,y:longint):longint;
begin
if x<y then min:=x else min:=y;
end;
begin
assign(input,'mouse.in');
reset(input);
assign(output,'mouse.out');
rewrite(output);
readln(n,m);
for i:= to n do begin
for j:= to m do
read(a[i,j]); readln; end;
for i:= to n do
for j:= to m do
begin
f[i,j,]:=maxlongint div ;f[i,j,]:=maxlongint div ;
end;
f[,,]:=a[,]+a[,]+a[,]; f[,,]:=a[,]+a[,]+a[,];
for i:= to n do
for j:= to m do
if (i<>)or(j<>) then
begin
f[i,j,]:=min(f[i-,j,]+a[i,j-],f[i-,j,])+a[i+,j]+a[i,j+];
f[i,j,]:=min(f[i,j-,]+a[i-,j],f[i,j-,])+a[i+,j]+a[i,j+];
end;
writeln(min(f[n,m,],f[n,m,]));
close(input); close(output);
end.
t2
题意:给出一个无向有权图,图的每个点为一个城市,我们说城市B愿意与城市A建立合作关系,当且仅当对于所有满足d(A,C)<=d(A,B)的城市C,都有R(C)<=R(B)。一个城市的受欢迎程度Bi定义为愿意与其建立合作关系的城市数量,求所有城市受欢迎度和(可以和自己建立关系)
分析:最短路,我们可以将条件转化为对于所有R(c)>R(B)的城市C,都有d(A,C)>d(A,B),我们设l[i]为满足R(x)>R(i)的点到i的最短路,从大到小枚举r的值,然后对R(i)=r的点做最短路,如果在这一过程中某个点d(i,j)<=l[j]说明不可行,则不去松弛。
代码:
program work;
type
point=^node;
node=record
x,v:longint; next:point;
end;
var
a:array[..]of point;
l,r,d,g,w,d1:array[..]of longint;
q:array[..]of longint;
n,i,m,ans,x,y,v,j:longint;
procedure add(x,y,v:longint);
var p:point;
begin
new(p); p^.x:=y; p^.v:=v; p^.next:=a[x]; a[x]:=p;
end;
procedure spfa(s:longint);
var h,t,x,y,k:longint; p:point;
begin
h:=; t:=; q[]:=s; d[s]:=; d1[s]:=; g[s]:=s;w[s]:=s; inc(ans);
while h<t do
begin
inc(h); x:=q[h]; new(p); p:=a[x]; g[x]:=;
if h>= then h:=;
while p<>nil do
begin
y:=p^.x; k:=d1[x]+p^.v;
if k<l[y] then
if (w[y]<>s)or(k<d1[y]) then
begin
d1[y]:=k; if d1[y]<d[y] then d[y]:=d1[y];
if w[y]<>s then begin w[y]:=s; inc(ans); end;
if g[y]<>s then
begin
g[y]:=s; inc(t); q[t]:=y;
if t>= then t:=;
end;
end;
p:=p^.next;
end;
end;
end;
begin
readln(n,m);
for i:= to n do readln(r[i]);
for i:= to m do
begin
readln(x,y,v); add(x,y,v); add(y,x,v);
end;
ans:=;
for i:= to n do l[i]:=maxlongint;
for i:= downto do
begin
for j:= to n do
begin d[j]:=maxlongint div ; g[j]:=; w[j]:=; end;
for j:= to n do
if r[j]=i then spfa(j);
for j:= to n do
if d[j]<l[j] then l[j]:=d[j];
end;
writeln(ans);
end.
最新文章
- Log4net入门(回滚日志文件篇)
- BZOJ 4619 Swap Space 解题报告
- C#中js文本提示
- Objective-C Block
- mysql字段不能为空的字段为空时也能插入的方法
- Uinty3d 镜面反射代码
- 【转】RTSP实例解析
- 一个简单的小例子让你明白c#中的委托-终于懂了!
- IComparer接口与
- 从最近MySQL的优化工作想到的
- indeed 第二次笔试题
- 杨佩昌:中国官员去德国考察看什么两眼发光 z
- ReactJS 生命周期、数据流与事件
- 5.npm scripts 使用指南
- 在Intellij idea 2017中运行tomcat 8.5
- Python距离放弃又近了Day02
- python WebDriver如何处理右键菜单
- Caffe和py-faster-rcnn日常使用备忘录
- 【Math】证明:实对称阵属于不同特征值的的特征向量是正交的
- L1-027 出租