JZOJ5907 轻功

Description

题目背景：
尊者神高达进入了基三的世界，作为一个 mmorpg 做任务是必不可少的，然而跑地图却令人十分不爽。好在基三可以使用轻功，但是尊者神高达有些手残，他决定用梅花桩练习轻功。
题目描述：
一共有 n 个木桩，要求从起点（0）开始，经过所有梅花桩，恰好到达终点 n,尊者神高达一共会 k 种门派的轻功，不同门派的轻功经过的梅花桩数不同，花费时间也不同。但是尊者神高达一次只能使用一种轻功，当他使用别的门派的轻功时，需要花费 W 秒切换（开始时可以是任意门派,不需要更换时间）。由于尊者神高达手残，所以经过某些梅花桩（包括起点和终点）时他不能使用一些门派的轻功。尊者神高达想知道他最快多久能到达终点如果无解则输出-1。

Input

第一行 n,k,W
接下来 k 行，每行为 ai 和 wi 代表第 i 种轻功花费 vi 秒经过 ai 个木桩。
接下来一行 Q 为限制条件数量。
接下来 Q 行，每行为 xi 和 ki 代表第 xi 个梅花桩不能使用第 ki 种门派的轻功经过。

Output

一行答案即所需最短时间。

Sample Input

Sample Input1：
6 2 5
1 1
3 10
2
1 1
2 1


Sample Input2：
6 2 5
1 1
3 10
0

Sample Output

Sample Output1：
18

样例解释 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:不可以

Solution

　　dp,用数组记录限制条件，手推一下就好了

 1 #include<cstdio>
 2 #define fo(a,b,c) for (int a=b;a<=c;a++)
 3 using namespace std;
 4 int n,k,w,q,a[107],b[107],d[507][107];
 5 bool f[507][1007];
 6 
 7 int min(int x,int y){
 8     if (x>y) return y;
 9     return x;
10 }
11 
12 int max(int x,int y){
13     if (x>y) return x;
14     return y;
15 }
16 
17 int main(){
18     scanf("%d%d%d",&n,&k,&w);    
19     fo(i,1,k)
20         scanf("%d%d",&a[i],&b[i]);
21     scanf("%d",&q);
22     fo(i,0,n)
23         fo(j,1,k){
24             f[i][j]=true;    
25             if (i!=0) d[i][j]=0xfffffff;
26         }
27     fo(i,1,q){
28         int x,y;
29         scanf("%d%d",&x,&y);
30         fo(j,max(0,x-a[y]),x)
31             f[j][y]=false;
32     }
33     fo(i,1,n)
34         fo(j,1,k)
35             if (i-a[j]>=0)
36                 if (f[i-a[j]][j])
37                     fo(t,1,k)
38                         if (j!=t&&i-a[j]!=0)
39                             d[i][j]=min(d[i][j],d[i-a[j]][t]+b[j]+w);
40                         else
41                             d[i][j]=min(d[i][j],d[i-a[j]][t]+b[j]);
42     int ans=0xfffffff;
43     fo(i,1,k)
44         ans=min(ans,d[n][i]);
45     if (ans==0xfffffff) printf("-1");
46     else printf("%d
",ans);
47 }

View Code