[dp][前缀和] Jzoj P5907 轻功(qinggong)

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;
保证数据合法

题解

• 数据这么小，各位大爷肯定都会做吧
• 考虑dp，设f[i][j]为走到第i个木桩，现在是用第j中轻功的最小时间
• 状态转移方程显然
• 那么，考虑一下题目的条件，有一些限制木桩不能用某些轻功经过
• 可以设g[i][j]为用j轻功到i有多少个没有的经过的木桩
• 剩下的平平常常都能A吧

代码

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const long long inf=0x3f3f3f3f3f3f;
int n,k,w,a[510],v[510],Q,g[510][110];
long long f[510][110],ans;
int main()
{
    //freopen("qinggong.in","r",stdin);
    //freopen("qinggong.out","w",stdout);
    scanf("%d%d%d",&n,&k,&w);
    for (int i=1;i<=k;i++) scanf("%d%d",&a[i],&v[i]);
    scanf("%d",&Q);
    for (int i=1,x,y;i<=Q;i++) scanf("%d%d",&x,&y),g[x][y]=1;
    for (int i=1;i<=k;i++) 
        for (int j=1;j<=n;j++)
            g[j][i]+=g[j-1][i];
    memset(f,125,sizeof(f));
    for (int i=1;i<=k;i++) f[0][i]=0;
    for (int i=0;i<=n;i++)
        for (int j=1;j<=k;j++)
            for (int z=1;z<=k;z++) 
                if (i+a[z]<=n&&(g[i+a[z]][z]-g[i][z]==0))
                {
                    if (j==z) f[i+a[z]][z]=min(f[i+a[z]][z],f[i][j]+v[z]);
                    else f[i+a[z]][z]=min(f[i+a[z]][z],f[i][j]+v[z]+w);
                }
    ans=inf;
    for (int i=1;i<=k;i++) ans=min(ans,f[n][i]);
    printf("%lld",ans==inf?-1:ans);
}