itdef

https://www.papamelon.com/problem/255

一個監獄里有 P 個并排著的牢房, 從左到右依次編號為 1,2,...P
最初所有的牢房里都住著一個囚犯。相鄰的兩個牢房之間有一個窗戶, 可以通過它與相鄰的牢房里的囚犯對話。
現在要釋放一批囚犯, 如果釋放某個牢房的囚犯, 其相鄰的牢房里的囚犯就會知道, 因而發怒暴動。
所以釋放某個牢房的囚犯時, 必須要賄賂兩旁相鄰的囚犯一枚金幣。
另外為了防止釋放的消息在相鄰牢房傳開, 不僅兩旁直接相鄰的牢房, 所有可能聽到消息的囚犯, 
即直到空牢房或者到監獄兩端為止, 此間的所有囚犯都必須給一枚金幣。
現在要釋放 a_1,a_2...a_Q牢房里的 Q 名囚犯, 釋放的順序還未確定。
如果選擇所需金幣數盡量少的順序釋放, 最少需要多少金幣？

輸入
第一行整數 T(1≤T≤100)，表示有多少組測試數據
每組測試數據有 2 行：
第一行有兩個整數 P 和 Q
第二行有 Q 個整數,表示 a_1,a_2...a_Q
1≤P≤10000,1≤Q≤100
輸出
輸出 T 行，每行格式：Case #{第幾組測試數據}: {答案}，表示第幾組測試數據，答案是多少
樣例 1
輸入
1
20 3
3 6 14
輸出
Case #1: 35

如圖

假如我們釋放14號牢房囚犯，那么計算當前需要的花費 ，再加上釋放1到13號房間中的3號和6號的囚犯的最小花費，就可以得到答案1
假如我們釋放3號牢房囚犯，那么計算當前需要的花費 ，再加上釋放4到20號房間中的14號和6號的囚犯的最小花費，就可以得到答案2
假如我們釋放6號牢房囚犯，那么計算當前需要的花費 ，再加上釋放1到5號房間中的3號囚犯的最小花費，再加上釋放7到20號房間中的14號囚犯的最小花費，就可以得到答案3
答案123中的最小花費就是最后的實際答案。
我們可以使用遞歸來計算 使用dp[x][y]記錄 釋放x到y之間所有囚犯的最小開銷。 但是由于P的范圍太大，數組內存過大，這里使用哈希表記錄釋放x到y之間所有囚犯的最小開銷。
用來避免重復計算.
代碼

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <unordered_map>

using namespace std;

int t, p, q;
const int N = 10010;
int arr[N];
unordered_map<long long, int > dp;

int dfs(int rooml, int roomr, int arrl, int arrr) {
	if (roomr < rooml) return 0;
	if (arrr < arrl) return 0;
	long long key = rooml + roomr * 100000;
	if (dp.count(key) != 0) return dp[key];
	//if (dp[rooml][roomr] != 0x3f3f3f3f) return dp[rooml][roomr];

	int ans  = 0x3f3f3f3f;
	for (int i = arrl; i <= arrr; i++) {
		int selRoom = arr[i];
		int c = (selRoom - rooml);
		int d = (roomr - selRoom);
		int a = dfs(rooml, selRoom - 1, arrl, i - 1);
		int b = dfs(selRoom + 1, roomr, i + 1, arrr);
		ans = min(ans, a + b + c + d);
	}
	dp[key] = ans;
	return ans;
}


void solve(int curr) {
	dp.clear();
	cin >> p >> q;
	for (int i = 1; i <= q; i++) {
		cin >> arr[i];
	}
	sort(arr + 1, arr + 1 + q);
	int ans = 0x3f3f3f3f;
	for (int i = 1; i <= q; i++) {
		int selRoom = arr[i];
		int c = (selRoom - 1);
		int d = (p - selRoom);
		int a = dfs(1, selRoom - 1, 1, i - 1);
		int b = dfs(selRoom + 1, p, i + 1, q);
		ans = min(ans, a + b + c + d);
	}

	cout << "Case #" << curr << ": " << ans << endl;
}


int main()
{
	cin >> t;
	for (int i = 1; i <= t; i++) {
		solve(i);
	}

	return 0;
}

下面再來一個dp數組優化內存版本的方案
使用dp[x][y]記錄 釋放x到y房間之間的所有囚犯的最小開銷。 但是由于P的范圍太大，數組內存過大.無法使用這個數組.
使用arr[N]的數組記錄要釋放的囚犯號碼， 可以考慮dp[x][y]表示釋放arr[x]~~arr[y]之間的所有囚犯的最小開銷。
dp[x][y] = min(dp[x][x+1]+dp[x+1][y] , dp[x][x+2],dp[x+2][y] ... ,dp[x][y-1]+dp[y-1][y]);

#include <iostream>
#include <memory.h>
#include <algorithm>

using namespace std;

const int N = 110;
int arr[N];
int dp[N][N];
int t, n, l;


int dpFunc(int l, int r) {
	if ( r <=l+1) {
		dp[l][r] = 0;
	}

	if (dp[l][r] != -1) return dp[l][r];
	int ans = 0x3f3f3f3f;
	for (int i = l + 1; i < r; i++) {
		ans = min(ans, (arr[r] - arr[i]-1)   + (arr[i]-arr[l]-1) + dpFunc(l, i) + dpFunc(i, r));
	}

	dp[l][r] = ans;
	return ans;
}

void solve(int currIdx) {
	cin >> l >> n;
	memset(arr, 0, sizeof arr);
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	//sort(&arr[1],&arr[1]+n);
	arr[0] = 0; arr[n + 1] = l + 1;
	memset(dp, -1, sizeof dp);

	int ans = dpFunc(0, n + 1);

	cout << "Case #" << currIdx << ": " << ans << endl;
	return ;
}

int main() {
	cin >> t;
	for (int i = 1; i <= t; i++) {
		solve(i);
	}

	return 0;
}

我的視頻題解空間