g498 - 兔子跳躍 (Rabbit)

🔗 前往 ZeroJudge 原題

題目描述

題目描述一隻兔子可以跳躍特定距離 x。給定三個跳躍距離 x，判斷兔子是否能跳到距離 x 的位置。

解題思路

這題可以使用動態規劃來解決。dp[i] 表示兔子是否能跳到位置 i。初始狀態 dp[0] = 1，表示兔子可以停留在起始位置。對於每個跳躍距離 x，如果 dp[i] = 1，則 dp[i+x] = 1，表示兔子可以從位置 i 跳到位置 i+x。最後，判斷 dp[x] 是否為 1，如果是，則輸出 "YES"，否則輸出 "NO"。由於題目輸入三個 x 值，且每次輸入後都進行更新，因此可以利用迴圈迭代三次。

複雜度分析

• 時間複雜度: O(5000)
• 空間複雜度: O(5000)

程式碼

#include <iostream>
using namespace std;
long long dp[5005]={1},x;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	for(int t=0;t<3;++t){
		cin >> x;
		for(int i=0;i+x<5000&&t!=2;++i){
			if(dp[i])dp[i+x]=1;
		}
		if(t==2){
			if(dp[x]){
				cout << "YES";
			}
			else{
				cout << "NO";
			}
		}
	}
}