【NOIP2018复习】B （DP）
B
时间限制:1000MS内存限制:256000KB
题目描述
题目背景：
ly童鞋上得厅堂下得厨房，左手羽毛右手乒乓，更不用说那精湛的铁头功夫了。然而从未接触过武侠的他并不擅长轻功，于是他决定用梅花桩练习轻功，从此出任CEO赢取白富美修身齐家治国平天下走上人生的巅峰
题目描述：
一共有 n 个木桩，要求从起点（0）开始，经过所有梅花桩，恰好到达终点 n,ly童鞋一共会 k 种门派的轻功，不同门派的轻功经过的梅花桩数不同，花费时间也不同。但是ly一次只能使用一种轻功，当他使用别的门派的轻功时，需要花费 W 秒切换（开始时可以是任意门派,不需要更换时间）。由于ly手（jio）残，所以经过某些梅花桩（包括起点和终点）时他不能使用一些门派的轻功。ly想知道他最快多久能到达终点，当然了如果无解则输出-1。
输入
第一行 n,k,W
接下来 k 行，每行为 ai 和 wi 代表第 i 种轻功花费 vi 秒经过 ai 个木桩。
接下来一行 Q 为限制条件数量。
接下来 Q 行，每行为 xi 和 ki 代表第 xi 个梅花桩不能使用第 ki 种门派的轻功经过。
输出
一行答案即所需最短时间。
输入样例复制
Sample Input1/qinggong.in：
6 2 5
1 1
3 10
2
1 1
2 1
Sample Input2/qinggong.out：
6 2 5
1 1
3 10
0
输出样例复制
样例解释 1：
先用第二种轻功花费 10 秒到 3，再用 5 秒切换到第一种轻功，最后再用 3 秒时间到 6.一共花费 10+5+3=18 秒
Sample Output2：
6
样例解释 2：
直接花费 6 秒到 6；
说明
Data Constraint 20%的数据 n<=20,k<=10,Q<=200; 对于另外 20%的数据 W=0 对于另外 20%的数据 Q=0 所以数据满足 n<=500,k<=100,Q<=50000,vi<=1e7; 保证数据合法 Hint Q:请问第一题可不可以往回跳 A:不可以 题目并不太难，同志仍须硬肝
题解：简单的DP, f[i,j]表示在第i个点以第j种轻功起跳的最小花费时间
预处理出每种轻功的非法起跳点和落地点
constmaxn=500;maxm=500;inf='1030t2.in';varf:array[0..maxn,0..100]of longint;vv,v:array[0..maxn,0..maxm]of boolean;a:array[0..maxn,1..2]of longint;n,m,i,j,w,k,ans,po:longint;procedure init;vari,q,x,y:longint;beginreadln(n,m,w);for i:=1 to m doreadln(a[i,1],a[i,2]);readln(q);for i:=1 to q dobeginreadln(x,y);vv[x,y]:=true;end;for i:=0 to n dofor j:=1 to m dofor k:=0 to a[j,1] doif i+k<=n thenif vv[i+k,j] then v[i,j]:=true;for i:=0 to n dofor j:=0 to m dof[i,j]:=maxlongint div 3;for i:=1 to m dof[0,i]:=0;end;function min(a,b:longint):longint;beginif an) then continue;if (vv[po,j]) then continue;if po=n thenbeginfor k:=1 to m dobegin// if vv[i+a[j,1],k] then continue;f[po,k]:=min(f[po,k],f[i,j]+a[j,2]);end;continue;end;for k:=1 to m dobeginif vv[po,k] then continue;if j<>k then f[po,k]:=min(f[po,k],f[i,j]+a[j,2]+w)elsef[po,k]:=min(f[po,k],f[i,j]+a[j,2]);end;end;ans:=maxlongint;for i:=1 to m dobeginans:=min(ans,f[n,i]);end;if ans=maxlongint div 3 then writeln(-1) else writeln(ans);// close(input);end.
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！