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

4bitにっき

ぽよ

AOJ0597 小籠包 (Xiao Long Bao)

DP メモ化再帰

解法

DP(メモ化再帰)。
手前7つの小籠包の食べる順番を状態にすれば、

dp[n][s]=n番目の小籠包の手前7つの食べる順がsであるとき、N番目~n番目の小籠包での最適解]
dp[n][s]=max(dp[n + 1][手前7つの食べる順について、小籠包nをi番目に挿入した場合の次の状態(0<=i<=7)] + (その時の、小籠包nと手前7つの間で増加した美味しさ))]

みたいな感じでDPができる。

実装

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

#define int long long

const int MAX_N = 100;

int N, D[MAX_N], A[MAX_N];
const int fac[8] = {1, 1, 2, 6, 24, 120, 720, 5040};

int ToHash(const vector<int> &v)
{
	int res = 0;
	bool isUsed[7] = {};
	for (int i = 0; i < v.size(); i++)
	{
		int cnt = 0;
		for (int j = 0; j != v[i]; j++)
		{
			if (!isUsed[j]) cnt++;
		}
		isUsed[v[i]] = true;
		//printf("%lld! * %lld\n", D - i - 1, cnt);
		res += fac[v.size() - i - 1] * cnt;
	}
	return res;
}

int memo[MAX_N][5040];

int DFS(int n, const vector<int> &v)
{
	if (n == N) return 0;
	int s = ToHash(v);
	if (memo[n][s] > 0) return memo[n][s];
	//i : n番目の小籠包の挿入位置
	for (int i = 0; i <= v.size(); i++)
	{
		vector<int> nv;
		nv.reserve(7);
		int pastSum = 0, futureSum = 0;
		//nv,pastSum,futureSumの計算
		for (int j = 0; j <= v.size(); j++)
		{
			if (j == i) nv.push_back(0);
			if (j == v.size()) continue;
			if (j < i && v[j] + 1 <= D[n - v[j] - 1]) pastSum += A[n - v[j] - 1];
			else if (j >= i && v[j] + 1 <= D[n]) futureSum += A[n];
			if (v[j] + 1 == 7) continue;
			nv.push_back(v[j] + 1);
		}
		//printf("%lld\n", futureSum);
		memo[n][s] = max(memo[n][s], DFS(n + 1, nv) + pastSum + futureSum);
	}
	return memo[n][s];
}

signed main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> D[i];
	}
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	printf("%lld\n", DFS(0, vector<int>()));
	return 0;
}