AOJ 0597 - Xiao Long Bao

問題文 : 小籠包

解法 :

周りに飛び散る範囲が狭いので, $dp[i][S] :=$ $i$ 番目から$i-6$ 番目までの小籠包を$S$ という順番で食べるときの美味しさの総和の最大値, としてdp.
見ている範囲から8 個以上離れている小籠包は今の状態に影響しないということをうまく活用する.

コード :

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int dp[128][5040];

map<vector<int>, int> enc;
map<int, vector<int> > dec;

int brute(int n, int *d, int *a)
{
	vector<int> v(n);
	int taste[128];
	for (int i = 0; i < n; i++) v[i] = i;
	
	int ans = 0, ctr = 0;
	do {
		int tmp = 0;
		memset(taste, 0, sizeof(taste));
		for (int i = 0; i < v.size(); i++){
			tmp += taste[v[i]];
			for (int _a = max(0, v[i] - d[v[i]]); _a <= min(n - 1, v[i] + d[v[i]]); _a++)
				taste[_a] += a[v[i]];
		}
		ans = max(ans, tmp);
		enc[v] = ctr;
		dec[ctr] = v;
		dp[n - 1][ctr++] = tmp;
	} while (next_permutation(v.begin(), v.end()));
	
	return (ans);
}

int main()
{
	int n;
	int d[128], a[128];
	
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++) scanf("%d", d + i);
	for (int i = 0; i < n; i++) scanf("%d", a + i);
	
	if (n <= 7) return (!printf("%d\n", brute(n, d, a)));
	else brute(7, d, a);
	
	for (int i = 7; i < n; i++){
		for (int j = 0; j < 5040; j++){
			vector<int> v = dec[j], next(8), form(7);
			//i - 7, i - 6, i - 5, i - 4, i - 3, i - 2, i - 1, i をそれぞれ0, 1, 2, 3, 4, 5, 6, 7 とする
			for (int pos = 0; pos < 8; pos++){
				next[pos] = 7;
				for (int k = 0; k < 7; k++){
					next[k + (k >= pos)] = v[k];
				}
				int tmp = 0;
				int taste[128] = {0};
				for (int k = 0; k < 8; k++){
					int p = i - 7 + next[k];
					tmp += taste[p];
					for (int _a = max(i - 7, p - d[p]); _a <= min(i, p + d[p]); _a++)
						if (_a == i || p == i) taste[_a] += a[p];
				}
				int ctr = 0;
				for (int k = 0; k < 8; k++) if (next[k] != 0) form[ctr++] = next[k] - 1;
				int e = enc[form];
				dp[i][e] = max(dp[i][e], dp[i - 1][j] + tmp);
			}
		}
	}
	
	printf("%d\n", *max_element(dp[n - 1], dp[n - 1] + 5040));
	
	return (0);
}