2024.6 -> 做题记录与方法总结

2024/6/15

1.P4363 [九省联考 2018] 一双木棋 chess

经典轮廓线dp
使用的关键在于发现状态数并不多,用 \(n\) 进制数来表现轮廓的状态

\(dp\) 的 转移 和 轮廓线 息息相关

如图,蓝色轮廓线状态只能转移到含一个紫色的状态
因为 $ 1 \leq n,m \leq 10$ 用 \(11\) 进制压缩状态就可以了

轮廓线状态压缩：

ll zip(int *now){
	ll res = 0;
	for(int i = n;i>=1;i--) res = res * 11 + now[i];
	return res; 
}

void unzip(ll S,int *now) {
	for(int i = 1;i<=n;i++) {
		now[i] = S % 11;
		S /= 11; 
	}
}	

\(AC-code\):

#include<bits/stdc++.h>
using namespace std;

int rd() {
	int x = 0, w = 1;
	char ch = 0;
	while (ch < '0' || ch > '9') {
		if (ch == '-') w = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + (ch - '0');
		ch = getchar();
	}
	return x * w;
}

void wt(int x) {
	static int sta[35];
	int f = 1;
	if(x < 0) f = -1,x *= f;
	int top = 0;
	do {
		sta[top++] = x % 10, x /= 10;
	} while (x);
	if(f == -1) putchar('-');
	while (top) putchar(sta[--top] + 48);
}

typedef long long ll;

int n,m;
int a[11][11],b[11][11];

unordered_map<ll,ll> dp;

ll zip(int *now){
	ll res = 0;
	for(int i = n;i>=1;i--) res = res * 11 + now[i];
	return res; 
}

void unzip(ll S,int *now) {
	for(int i = 1;i<=n;i++) {
		now[i] = S % 11;
		S /= 11; 
	}
}	

const ll inf = 1e9;

ll dfs(ll S){
	if(dp.count(S)) return dp[S];
	int size = 0;
	int *now = new int[11];
	unzip(S,now);
	for(int i = 1;i<=n;i++) size += now[i];
	int re = (size & 1) ? inf:-inf;
	for(int i = 1;i<=n;i++) {
		if((i == 1 && now[i] < m) || (i != 1 && now[i] < now[i-1])) {
			now[i]++;
			if((size & 1)) re = min((ll)re,dfs(zip(now)) - b[i][now[i]]);
			else re = max((ll)re,dfs(zip(now)) + a[i][now[i]]);
			now[i]--;
		}
	}
	delete now;
	return dp[S] = re;
}

signed main() {
	n = rd(),m = rd();
	for(int i = 1;i<=n;i++) 
		for(int j = 1;j<=m;j++) 
			a[i][j] = rd();
	for(int i = 1;i<=n;i++) 
		for(int j = 1;j<=m;j++) 
			b[i][j] = rd();

	ll ed = 0;
	for(int i = 1;i<=n;i++) ed = ed * 11 + m;
	dp[ed] = 0;
	ll ans = dfs(0);
	wt(ans);
	return 0;
}