AOJ0597 小籠包 (Xiao Long Bao)
解法
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; }