P1541

简单四维dp。

#include<bits/stdc++.h>
using namespace std;
int a[355],b,t[5],dp[45][45][45][45];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m,r;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	dp[0][0][0][0]=a[1];
	for(int i=1;i<=m;i++)cin>>b,t[b]++;
	for(int i=0;i<=t[1];i++){
		for(int j=0;j<=t[2];j++){
			for(int k=0;k<=t[3];k++){
				for(int l=0;l<=t[4];l++){
					r=1+i+j*2+k*3+l*4;
					if(i!=0)dp[i][j][k][l]=max(dp[i][j][k][l],dp[i-1][j][k][l]+a[r]); 
					if(j!=0)dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j-1][k][l]+a[r]);
					if(k!=0)dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j][k-1][l]+a[r]);
					if(l!=0)dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j][k][l-1]+a[r]);
				}
			}
		}
	}
	cout<<dp[t[1]][t[2]][t[3]][t[4]];
}