5907.【NOIP 2018シミュレーション10.16】軽功()

テーマ:
全部でn個の杭があり、起点(0)からすべての梅の杭を経て、ちょうど終点nに着くことを要求し、尊者神ガンダムは全部でk種の門派の軽功に達し、門派によって軽功が通った梅の杭数が異なり、時間もかかる.しかし尊者神ガンダムは一度に1つの軽功しか使用できず、他の門派の軽功を使用する場合はW秒切替(開始時は任意の門派であり、時間の交換は不要)が必要となる.尊者神は手が不自由なので、いくつかの梅の杭(起点と終点を含む)を通るとき、門派の軽功を使うことができません.尊者神ガンダムは彼が最速でどのくらいでゴールに着くことができるか知りたいです.もし解けなければ-1を出力します.
考え方:
明らかに代価はいくつか目の柱と前回使ったどんな功法と関係があるだけで、それから跳ぶ時の間に特殊な柱があってはいけないので、私たちは最初にどの点が歩けるかを前処理して、それから柱と功法を列挙して直接dpすればいいです.
プログラム:

#include
#include
#include
#include
#define LL long long
using namespace std;
const int N=1005;
LL ans,n,k,W,a[N],w[N],q,x,p;
LL h[N][N],f[N][N];
int main(){
	freopen("qinggong.in","r",stdin);
	freopen("qinggong.out","w",stdout);
	scanf("%lld%lld%lld",&n,&k,&W);
	for (LL i=1;i<=k;i++) scanf("%lld%lld",&a[i],&w[i]);
	scanf("%lld",&q);
	for (LL i=1;i<=q;i++) {
		scanf("%lld%lld",&x,&p);
		h[x][p]=1;
		for (LL j=1;j<=a[p];j++) h[x+j][p]=1;
	}
	memset(f,31,sizeof(f));
	for (LL i=1;i<=k;i++) f[0][i]=0;
	for (LL i=1;i<=n;i++)
	 for (LL j=1;j<=k;j++)
	  if (!h[i][j]){
	  	for (LL ii=1;ii<=k;ii++)
	  		if (ii==j&&i-a[j]>=0) f[i][j]=min(f[i][j],f[i-a[j]][ii]+w[j]);
	  	 		else if (i-a[j]>=0) f[i][j]=min(f[i][j],f[i-a[j]][ii]+w[j]+W);	
	  }
	ans=12345678900;
	for (LL i=1;i<=k;i++) ans=min(ans,f[n][i]);
	if (ans==12345678900) printf("-1");
				else printf("%lld",ans);
}