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 1Sample 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吧

代碼

1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 using namespace std; 5 const long long inf=0x3f3f3f3f3f3f; 6 int n,k,w,a[510],v[510],Q,g[510][110]; 7 long long f[510][110],ans; 8 int main() 9 { 10 //freopen("qinggong.in","r",stdin); 11 //freopen("qinggong.out","w",stdout); 12 scanf("%d%d%d",&n,&k,&w); 13 for (int i=1;i<=k;i++) scanf("%d%d",&a[i],&v[i]); 14 scanf("%d",&Q); 15 for (int i=1,x,y;i<=Q;i++) scanf("%d%d",&x,&y),g[x][y]=1; 16 for (int i=1;i<=k;i++) 17 for (int j=1;j<=n;j++) 18 g[j][i]+=g[j-1][i]; 19 memset(f,125,sizeof(f)); 20 for (int i=1;i<=k;i++) f[0][i]=0; 21 for (int i=0;i<=n;i++) 22 for (int j=1;j<=k;j++) 23 for (int z=1;z<=k;z++) 24 if (i+a[z]<=n&&(g[i+a[z]][z]-g[i][z]==0)) 25 { 26 if (j==z) f[i+a[z]][z]=min(f[i+a[z]][z],f[i][j]+v[z]); 27 else f[i+a[z]][z]=min(f[i+a[z]][z],f[i][j]+v[z]+w); 28 } 29 ans=inf; 30 for (int i=1;i<=k;i++) ans=min(ans,f[n][i]); 31 printf("%lld",ans==inf?-1:ans); 32 }

?

轉載于:https://www.cnblogs.com/Comfortable/p/9802517.html

總結

以上是生活随笔為你收集整理的[dp][前缀和] Jzoj P5907 轻功(qinggong)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。