d874 - 4. 階梯問題
題目描述
題目要求計算從 1 出發，每次可以走 1 到 L 的距離，且每次走的距離只能是前一次的 ±1 或不變，到達 L 的最少步數。
解題思路
題目可以轉換為尋找一個序列，序列的起始值為 1，結束值為 L，且序列中相鄰元素之差的絕對值不超過 1。要求序列的長度最小。
觀察題目範例，可以發現當 L 為奇數時，最少步數為 L，序列為 1, 2, 3, ..., L。當 L 為偶數時，最少步數為 L，序列為 1, 2, 3, ..., L-1, L。
程式碼預先計算了 dp 陣列，dp[i] 儲存了到達 i 的最少步數。dp 陣列的生成方式是交替填充 c 和 c+1，其中 c 從 1 開始，每次增加 2。這樣可以確保在到達 i 時，找到的是最少步數。
程式碼直接讀取輸入 L，然後輸出 dp[L] 的值。
複雜度分析
- 時間複雜度: O(1)
- 空間複雜度: O(N)，其中 N 是 dp 陣列的大小 (20001)。
程式碼
#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>
using namespace std;
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
int stk[4],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int dp[20001];
int main(){
for(int i(1),c(1),z,cc(1);i<=20001;c+=2,++cc){
for(z=0;z<cc;++z)
dp[i++]=c;
for(z=0;z<cc;++z)
dp[i++]=c+1;
}
int a;
while(a=read()){
write(dp[a]);
putchar_unlocked(10);
}
}