g308 - pB. 跳跳布朗尼(Brownie)

🔗 前往 ZeroJudge 原題

題目描述

題目描述了一個由 N 個格子組成的序列，每個格子都有一個傳送點指向另一個格子。從一個起始格子 T 開始，按照傳送點的指示跳轉，直到跳轉到已經走過的格子。每個格子可能有一個布朗尼，目標是計算在跳轉過程中最多可以吃到的布朗尼數量。傳送點在被觸發後會被破壞，避免重複跳轉。

解題思路

這題的核心是模擬跳轉的過程，並記錄已經走過的格子。使用一個陣列 a 儲存每個格子的傳送點資訊，另一個陣列（題目中隱含在輸入的第三行）儲存每個格子是否有布朗尼。從起始格子 T 開始，不斷按照傳送點跳轉，同時檢查當前格子是否有布朗尼，如果有則增加布朗尼數量。在跳轉之前，將當前格子的傳送點設為 -1，表示該傳送點已被破壞。當跳轉到一個傳送點為 -1 的格子時，表示已經走過該格子，跳轉結束。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
int n,a[1005][2],ans,it;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> it;
	for(int i=0;i<n;++i){
		cin >> a[i][0];
	}
	for(int i=0;i<n;++i){
		cin >> a[i][1];
	}
	while(a[it][1]!=-1){
		ans+=a[it][1];
		a[it][1]=-1;
		it=a[it][0];
	}
	cout << ans;
}