AOJ 0597: Xiao Long Bao

解法

直近の順列に着目して、DPする

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define chmax(X,Y) X=max(X,Y)
#define N 200
map<vector<int>, int> dp[N];

int main(){
	int n;
	cin>>n;
	vector<int> d(n), a(n);
	for(int i = 0; i < n; i++) cin>>d[i];
	for(int i = 0; i < n; i++) cin>>a[i];
	int m = min(n, 7);
	vector<int> x(m);
	for(int i = 0; i < m; i++) x[i] = i;
	vector<int> y(x);
	do{
		int r = 0;
		for(int i = 0; i < m; i++)
			for(int j = max(0, i-d[i]); j <= min(m-1, i+d[i]); j++)
				if(x[i]<x[j]) r += a[i];
		dp[m][x] = r;
	} while(next_permutation(x.begin(), x.end()));
	for(int i = m; i < n; i++){
		x = vector<int>(y);
		do{
			int rr = dp[i][x];
			vector<int> x2(m);
			for(int j = 0; j < m-1; j++){
				x2[j] = x[j+1];
				if(x2[j]<x[0]) x2[j]++;
			}
			x2[m-1] = 0;
			for(int j = 0; j < m; j++){
				int r = rr;
				if(x[0]<x2[m-1] && m<=d[i-m]) r += a[i-m];
				else if(x[0]==x2[m-1]){
					int r1 = m<=d[i-m]?a[i-m]:0;
					int r2 = m<=d[i]?a[i]:0;
					r += max(r1, r2);
				} else if(x[0]>x2[m-1] && m<=d[i]) r += a[i];
				for(int k = 0; k < m-1; k++){
					int k2 = i-m+k+1;
					if(x2[k]<x2[m-1] && abs(m-1-k)<=d[k2]) r += a[k2];
					else if(x2[k]>x2[m-1] && abs(m-1-k)<=d[i]) r += a[i];
				}
				chmax(dp[i+1][x2], r);
				x2[m-1]++;
				for(int k = 0; k < m-1; k++)
					if(x2[k]==x2[m-1]) x2[k]--;
			}
		} while(next_permutation(x.begin(), x.end()));
	}
	x = vector<int>(y);
	int res = 0;
	do{
		chmax(res, dp[n][x]);
	} while(next_permutation(x.begin(), x.end()));
	cout<<res<<endl;
	return 0;
}