[插头DP自我总结]

时间：2023-03-10 05:55:42
[插头DP自我总结]

[HNOI 2007]神奇游乐园

#include <bits/stdc++.h>

#define maxn 110

using namespace std;

typedef long long ll;

int n, m;

int a[maxn][maxn];

ll ans = -1ll << 60;

#define M 2000010

#define mod 997

struct Hashmap{

	ll st[M];

	int h[1000], size, nxt[M];

	ll f[M];

	void clear(){memset(h, 0, sizeof h); size = 0;}

	void push(ll hash_, ll val){

		int tmp = hash_ % mod;

		for(int i = h[tmp]; i; i = nxt[i]){

			if(st[i] == hash_){

				f[i] = max(f[i], val);

				return;

			}

		}

		int now = ++ size;

		f[now] = val;

		st[now] = hash_;

		nxt[now] = h[tmp];

		h[tmp] = now;

	}

}dp[2];

int cur, code[20], ch[20];

void Decode(ll st){

	for(int i = m; i >= 0; i --)

	    code[i] = st & 7, st >>= 3;

}

ll Encode(){

	ll ret = 0;

	memset(ch, -1, sizeof ch);

	ch[0] = 0; int cnt = 0;

	for(int i = 0; i <= m; i ++){

		if(ch[code[i]] == -1)ch[code[i]] = ++ cnt;

		code[i] = ch[code[i]];

		ret = ret << 3 | code[i];

	}

	return ret;

}

void Shift(){

	for(int i = m; i >= 1; i --)

	    code[i] = code[i-1];

	code[0] = 0;

}

inline void Change(int u, int v){

	for(int i = 0; i <= m; i ++)

	    if(code[i] == v)

	        code[i] = u;

}

void DP(int i, int j){

	dp[cur^1].clear();

	for(int k = 1; k <= dp[cur].size; k ++){

		Decode(dp[cur].st[k]);

		if(j == 1){if(code[m])continue;Shift();}

		int Left = code[j-1], Up = code[j];

		if(Left && Up){

			code[j] = code[j-1] = 0;

			if(Left == Up){

                ll ENCODE = Encode();

				if(ENCODE == 0)ans = max(ans, dp[cur].f[k] + a[i][j]);

			}

			else{

                Change(Left, Up);

                dp[cur^1].push(Encode(), dp[cur].f[k] + a[i][j]);

			}

		}

		else if(Left || Up){

			int tmp = Left ? Left : Up;

			code[j-1] = 0, code[j] = tmp;

			dp[cur^1].push(Encode(), dp[cur].f[k] + a[i][j]);

			code[j] = 0, code[j-1] = tmp;

			dp[cur^1].push(Encode(), dp[cur].f[k] + a[i][j]);

		}

		else{

            dp[cur^1].push(Encode(), dp[cur].f[k]);

            code[j] = code[j-1] = 8;

            dp[cur^1].push(Encode(), dp[cur].f[k] + a[i][j]);

		}

	}

	cur ^= 1;

}

int main(){

#ifndef ONLINE_JUDGE

    freopen("park.in","r",stdin);

    freopen("park.out","w",stdout);

#endif

	scanf("%d%d", &n, &m);

	for(int i = 1; i <= n; i ++)

		for(int j = 1; j <= m; j ++)

			scanf("%d", &a[i][j]);

	dp[cur].clear();

	dp[cur].push(0, 0);

	for(int i = 1; i <= n; i ++)

		for(int j = 1; j <= m; j ++)

		    DP(i, j);

	printf("%lld\n", ans);

	return 0;

}

粘了一个模板上来=-=

基于连通性的动态规划，最小表示法很好用。

我们可以用一个压缩的数字表示一个连通情况，比如DP生成树，概率，棋盘上格子的情况，等等等

只要和连通性有关而且n很小时就可以用啦QAQ。

又忘了模板了QAQ

就是如果左边和上面是一个连通分量即Left == Up时，我们要合并连通分量，所以此时已经出现了一个圈了，这道题不能有多个圈，所以最后不放进去

code[j] = code[j-1] = 0.

[BZOJ 3753]Wall

扩展一下方格变成一个回路问题，然后射线法判断格子是否内部。

出现的问题是当left == up时，code[j] = code[j-1] = 0，然后再改所有的标号

当必须只能有一个回路的时候，Encode()一定要等于0.

#include <bits/stdc++.h>

#define maxn 20

using namespace std;

typedef long long ll;

int n, m;

int need[maxn][maxn], a[maxn][maxn];

int cur = 0, Cnt, cnt;

const int md = 997;

struct Hashmap{

	#define M 2000010

	ll st[M];

	int f[M], h[1000], nxt[M], size;

	void init(){

		memset(h, 0, sizeof h);

		size = 0;

	}

	void push(ll hs, int val){

		int tmp = hs % md;

		for(int i = h[tmp]; i; i = nxt[i]){

			if(st[i] == hs){

				f[i] = max(f[i], val);

				return;

			}

		}

		int now = ++ size;

		f[now] = val;

		nxt[now] = h[tmp];

		st[now] = hs;

		h[tmp] = now;

	}

}dp[2];

int code[maxn], ch[maxn];

void Decode(ll st){

	for(int i = m; i >= 0; i --)

	    code[i] = st & 7, st >>= 3;

}

ll Encode(){

	ll ret = 0;

	memset(ch, -1, sizeof ch);

	ch[0] = 0; int cnt = 0;

	for(int i = 0; i <= m; i ++){

		if(ch[code[i]] == -1)

		    ch[code[i]] = ++ cnt;

		code[i] = ch[code[i]];

		ret <<= 3;

		ret |= code[i];

	}return ret;

}

void Shift(){

	for(int i = m; i; i --)

	    code[i] = code[i-1];

	code[0] = 0;

}

bool Judge(int cnt, int i, int j){

	if(cnt && need[i][j] == 1)return false;

	if(!cnt && need[i][j] == 2)return false;

	return true;

}

int ans = -0x7fffffff;

void Trans(int i, int j){

	dp[cur^1].init();

	for(int k = 1; k <= dp[cur].size; k ++){

		Decode(dp[cur].st[k]);

		if(j == 1){if(code[m])continue;Shift();}

		int lf = code[j-1], up = code[j], sta = 0;

		for(int p = 0; p < j-1; p ++)

		    sta ^= (code[p] != 0);

		if(lf && up){

            code[j] = code[j-1] = 0;

			if(lf == up){

				if(Encode() == 0 && cnt == Cnt)//here!

					ans = max(ans, dp[cur].f[k]);

			}

			else{

				if(Judge(sta, i, j)){

					for(int p = 0; p <= m; p ++)

					    if(code[p] == up)

					        code[p] = lf;

					dp[cur^1].push(Encode(), dp[cur].f[k] + sta * a[i][j]);

				}

			}

		}

		else if(lf || up){

			int tmp = lf ? lf : up;

			if(Judge(sta, i, j)){

                code[j-1] = 0, code[j] = tmp;

                dp[cur^1].push(Encode(), dp[cur].f[k] + sta * a[i][j]);

			}

			sta ^= 1;

			if(Judge(sta, i, j)){

				code[j] = 0, code[j-1] = tmp;

				dp[cur^1].push(Encode(), dp[cur].f[k] + sta * a[i][j]);

			}

		}

		else{

			if(Judge(sta, i, j))

				dp[cur^1].push(Encode(), dp[cur].f[k] + sta * a[i][j]);

			sta ^= 1;

            if(Judge(sta, i, j)){

				code[j] = code[j-1] = 15;

				dp[cur^1].push(Encode(), dp[cur].f[k] + sta * a[i][j]);

            }

		}

	}

	if(need[i][j] == 2)cnt ++;

	cur ^= 1;

}

int main(){

	scanf("%d%d", &n, &m);

	for(int i = 1; i <= n; i ++)

		for(int j = 1; j <= m; j ++)

		    scanf("%d", &a[i][j]);

    n ++, m ++;

    dp[cur].init();

    dp[cur].push(0, 0);

    for(int i = 1; i <= n; i ++)

		for(int j = 1; j <= m; j ++)

		    Trans(i, j);

	printf("%d\n", ans);

    for(int i = 1; i < n; i ++)

		for(int j = 1; j < m; j ++)

		    scanf("%d", &need[i][j]), Cnt += need[i][j] == 2;

	ans = -0x7fffffff;

	dp[cur].init();

	dp[cur].push(0, 0);

	for(int i = 1; i <= n; i ++)

		for(int j = 1; j <= m; j ++)

		    Trans(i, j);

	if(ans < -0x7ffffff)printf("Can not establish GFW.");

	else printf("%d\n", ans);

	return 0;

}

相关文章