题目

解题思路

设$f[i][j]$f[i][j]表示跳到第i ii个梅花桩，准备用$j$j轻功跳下一个梅花桩的最小时间花费。
那么很明显我们要枚举是用哪一个轻功飞到第$i$i个梅花桩的。那么再在第三重循环$k$k枚举。
那么如果$j=k$j=k，就不用花费$s$s去切换，就有：
f[i][j]=min(f[i][j],f[i−a[j].f][k]+a[j].t) f[i][j]=min(f[i][j],f[i-a[j].f][k]+a[j].t)
f[i][j]=min(f[i][j],f[i−a[j].f][k]+a[j].t)

如果$j!=k$j!=k，那么久在后面加一个$s$s即可。
$f[i][j]=min(f[i][j],f[i−a[j].f][k]+a[j].t+s) f[i][j]=min(f[i][j],f[i-a[j].f][k]+a[j].t+s) f[i][j]=min(f[i][j],f[i−a[j].f][k]+a[j].t+s)$f[i][j]=min(f[i][j],f[i−a[j].f][k]+a[j].t+s)f[i][j]=min(f[i][j],f[i−a[j].f][k]+a[j].t+s)f[i][j]=min(f[i][j],f[i−a[j].f][k]+a[j].t+s)

答案就是$min(f[n][i])(1≤i≤m)$min(f[n][i])(1≤i≤m)
时间复杂度$O(n^2m)$O(n2m)

代码

#include<cstdio>
#include<iostream>
#define rr register 
using namespace std;
int n,K,W,Q; bool b[510][110]; long long ans=1e17,f[510][110]; 
struct node{int x,y;}a[510];
inline long long minn(long long x,long long y){if (x<y) return x; return y;}
inline bool check(int x,int y,int t)
{for (rr int i=x;i<=y;i++) if (b[i][t]==1) return 0; return 1;}
int main()
{
	scanf("%d%d%d",&n,&K,&W); 
	for (rr int i=1;i<=K;i++) scanf("%d%d",&a[i].x,&a[i].y);	
	scanf("%d",&Q); int xx,yy; 
	for (rr int i=1;i<=Q;i++) scanf("%d%d",&xx,&yy),b[xx][yy]=1; 
	for (rr int i=0;i<=n;i++) for (rr int j=1;j<=K;j++) f[i][j]=1e17; 
	for (rr int i=1;i<=K;i++) if (!b[0][i]) f[0][i]=0;
	for (rr int i=1;i<=n;i++) 
	 for (rr int j=1;j<=K;j++)
	 if (i-a[j].x>=0&&check(i-a[j].x,i,j)){
	    for (rr int k=1;k<=K;k++)
	    if (j!=k)
	     f[i][j]=minn(f[i][j],f[i-a[j].x][k]+(long long)a[j].y+(long long)W);
	    else 
	     f[i][j]=minn(f[i][j],f[i-a[j].x][k]+(long long)a[j].y);
	 }
	for (rr int i=1;i<=K;i++) 
	 if (!b[n][i])
	  ans=minn(ans,f[n][i]);
	if (ans<1e17) printf("%lld",ans); else printf("-1"); 
	return 0; 
}