活動(dòng)地址： ?？痛赫兴㈩}訓(xùn)練營(yíng) - 編程打卡活動(dòng)

簡(jiǎn)單題 小紅結(jié)賬

1. 初始化數(shù)據(jù)結(jié)構(gòu)：
   • 使用一個(gè)大小為 m+1 的數(shù)組 s 來(lái)記錄每個(gè)人的轉(zhuǎn)賬總額。下標(biāo) 1 到 m 表示每個(gè)人， s[i] 表示第 i 個(gè)人需要轉(zhuǎn)賬的總金額。
2. 逐張?zhí)幚碣~單：
   • 對(duì)于每張賬單：
     • 計(jì)算每個(gè)人的分?jǐn)偨痤~ cost = ?c / k?，公式為 (c + k - 1) / k（這是向上取整的一種實(shí)現(xiàn)方式）。
     • 讀取 k-1 個(gè)人的編號(hào)，并將 cost 累加到對(duì)應(yīng)人的轉(zhuǎn)賬金額上。
3. 輸出結(jié)果：
   • 遍歷數(shù)組 s 中從 1 到 m 的部分，依次輸出每個(gè)人的轉(zhuǎn)賬總額。

package main

import "fmt"

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	s := make([]int, m+1)
	for i := 1; i <= n; i++ {
		var k, c int
		fmt.Scan(&k, &c)
		cost := (c + k - 1) / k
		for j := 1; j <= k-1; j++ {
			var x int
			fmt.Scan(&x)
			s[x] += cost
		}
	}
	for i := 1; i <= m; i++ {
		fmt.Print(s[i], " ")
	}
}

中等題 跳躍游戲(一)

1. 初始化動(dòng)態(tài)規(guī)劃數(shù)組

• 定義一個(gè)數(shù)組 dp，其中 dp[i] 表示從數(shù)組的起始位置（索引 0）出發(fā)，能夠到達(dá)的最遠(yuǎn)位置。
• 初始值 dp[0] = a[0]，即從第一個(gè)位置出發(fā)時(shí)能夠到達(dá)的最遠(yuǎn)位置就是 a[0]。

2. 動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移

• 遍歷數(shù)組中的每個(gè)位置 i（從 1 開(kāi)始），更新 dp[i]
  • 如果當(dāng)前的最遠(yuǎn)可達(dá)位置 dp[i-1] 已經(jīng)大于等于 i，說(shuō)明我們能夠到達(dá)位置 i
    • 在這種情況下，更新 dp[i] 為 max(dp[i-1], i + a[i])，即比較之前的最遠(yuǎn)可達(dá)位置和從當(dāng)前位置 i 能夠跳躍到的最遠(yuǎn)位置。
  • 如果 dp[i-1] < i，說(shuō)明無(wú)法到達(dá)位置 i，此時(shí)也不需要繼續(xù)計(jì)算，因?yàn)楹罄m(xù)位置也無(wú)法到達(dá)。

3. 判斷結(jié)果

• 最后檢查 dp[n-1] 是否大于等于 n-1
  • 如果 dp[n-1] >= n-1，說(shuō)明可以跳到數(shù)組的最后一個(gè)位置，輸出 true。
  • 否則，輸出 false。

package main

import "fmt"

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}
	dp := make([]int, n)
	dp[0] = a[0]
	for i := 1; i < n; i++ {
		dp[i] = dp[i-1]
		if dp[i] >= i {
			dp[i] = max(dp[i], i+a[i])
		}
	}
	if dp[n-1] >= n-1 {
		fmt.Println("true")
	} else {
		fmt.Println("false")
	}
}

困難題 郊區(qū)春游

1. 預(yù)處理最短路徑

• 使用 Floyd-Warshall 算法計(jì)算所有節(jié)點(diǎn)之間的最短路徑。
  • 初始化一個(gè)二維數(shù)組 d，其中 d[i][j] 表示從節(jié)點(diǎn) i 到節(jié)點(diǎn) j 的最短距離。
  • 如果 i = j ，則 d[i][j] = 0；如果 i 和 j 之間沒(méi)有直接連通，則 d[i][j] = ∞。
  • 遍歷所有邊，更新直接相連節(jié)點(diǎn)之間的距離。
  • 使用三重循環(huán)（Floyd-Warshall 算法的核心部分），逐步更新任意兩點(diǎn)之間的最短路徑。

2. 狀態(tài)壓縮動(dòng)態(tài)規(guī)劃

• 定義狀態(tài) dp[mask][i]：
  • mask 是一個(gè)二進(jìn)制數(shù)，表示當(dāng)前已經(jīng)訪問(wèn)的郊區(qū)集合。例如，mask = 0101 表示訪問(wèn)了第 1 和第 3 個(gè)郊區(qū)。
  • i 表示當(dāng)前所在的郊區(qū)編號(hào)。
  • dp[mask][i] 表示在訪問(wèn)了 mask 中的所有郊區(qū)，并且最后停留在郊區(qū) ( i ) 時(shí)的最小花費(fèi)。
• 初始化：
  • 對(duì)于每個(gè)郊區(qū) i ，單獨(dú)訪問(wèn)它時(shí)的花費(fèi)為 0，即 dp[1<<i][i] = 0。
• 狀態(tài)轉(zhuǎn)移：
  • 枚舉當(dāng)前的狀態(tài) mask 和當(dāng)前所在的郊區(qū) j 。
  • 如果 j 已經(jīng)被訪問(wèn)過(guò)（即 (mask >> j) & 1 == 1），嘗試從未訪問(wèn)過(guò)的郊區(qū) ( k ) 轉(zhuǎn)移到 ( j )。
  • 更新?tīng)顟B(tài)：dp[mask | (1<<k)][k] = min(dp[mask | (1<<k)][k], dp[mask][j] + d[v[j]][v[k]])，其中 d[v[j]][v[k]] 是從郊區(qū) ( v[j] ) 到郊區(qū) ( v[k] ) 的最短距離。

3. 最終結(jié)果

• 遍歷所有可能的終點(diǎn) i ，找到訪問(wèn)了所有 r 個(gè)郊區(qū)后的最小花費(fèi)：
  • ans = min(ans, dp[(1<<r)-1][i])，其中 (1<<r)-1 表示所有郊區(qū)都被訪問(wèn)的狀態(tài)。

package main

import (
	"fmt"
	"math"
)

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	var n, m, r int
	fmt.Scan(&n, &m, &r)
	v := make([]int, r)
	for i := 0; i < r; i++ {
		fmt.Scan(&v[i])
	}
	d := make([][]int, n+1)
	for i := 1; i <= n; i++ {
		d[i] = make([]int, n+1)
		for j := 1; j <= n; j++ {
			if i == j {
				d[i][j] = 0
			} else {
				d[i][j] = math.MaxInt
			}
		}
	}
	for i := 0; i < m; i++ {
		var a, b, c int
		fmt.Scan(&a, &b, &c)
		d[a][b] = min(d[a][b], c)
		d[b][a] = min(d[b][a], c)
	}
	for k := 1; k <= n; k++ {
		for i := 1; i <= n; i++ {
			for j := 1; j <= n; j++ {
				if d[i][k] != math.MaxInt && d[k][j] != math.MaxInt {
					d[i][j] = min(d[i][j], d[i][k]+d[k][j])
				}
			}
		}
	}

	dp := make([][]int, 1<<r)
	for i := 1; i < (1 << r); i++ {
		dp[i] = make([]int, r)
		for j := 0; j < r; j++ {
			dp[i][j] = math.MaxInt
		}
	}
	for i := 0; i < r; i++ {
		dp[1<<i][i] = 0
	}
	for i := 1; i < (1<<r)-1; i++ {
		for j := 0; j < r; j++ {
			if (i>>j)&1 == 0 {
				continue
			}
			for k := 0; k < r; k++ {
				if (i>>k)&1 == 0 {
					if d[v[j]][k] != math.MaxInt {
						dp[i|(1<<k)][k] = min(dp[i|(1<<k)][k], dp[i][j]+d[v[j]][v[k]])
					}
				}
			}
		}
	}
	ans := math.MaxInt
	for i := 0; i < r; i++ {
		ans = min(ans, dp[(1<<r)-1][i])
	}
	fmt.Println(ans)
}