読者です 読者をやめる 読者になる 読者になる

Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

AOJ 0597 - Xiao Long Bao

動的計画法 JOI

問題文 : 小籠包


解法 :

周りに飛び散る範囲が狭いので, $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);
}