b672 - A Special Automobile Race
題目描述
題目描述一個特殊的汽車競賽，競賽的目標不是速度，而是數學能力。賽道上有 n 個休息站，每個休息站的汽車可以行駛不同的距離。玩家必須在每個休息站更換汽車。目標是找到到達終點所需的最小休息站數量。起始點的汽車至少可以行駛到下一個 5 個休息站。
解題思路
這題可以使用動態規劃來解決。dp[i] 表示到達第 i 個休息站所需的最小休息站數量。初始化 dp[0] = 0。對於每個休息站 i，我們遍歷它可以到達的所有休息站 j（從 i+1 到 min(a+i, n)），如果 dp[j] 尚未被更新，則更新 dp[j] = dp[i] + 1。如果 dp[j] 已經被更新，則取 dp[j] 和 dp[i] + 1 的最小值。由於題目要求最小的休息站數量，且起始點可以到達下一個 5 個休息站，因此可以視為一個貪心策略的動態規劃問題。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(n)
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,a;
while(n=read()){
if(!n)break;
int dp[n+1]={0};
for(int i=0;i<n;++i){
a=read();
for(int j=i+1,k=dp[i]+1,z=min(a+i,n);j<=z;++j)
if(j>4)
(!dp[j])?dp[j]=k:dp[j]=min(k,dp[j]);
}
cout << dp[n] << "\n";
}
}