[HOJ] 296 - 烏龜棋

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 40
int dp[N][N][N][N]={0},s[355];
int dfs(int a,int b,int c,int d){
    if(dp[a][b][c][d]) return dp[a][b][c][d];
    if(a+b+c+d==0) return 0;
    int tmp,_max=0,all=a+b*2+c*3+d*4;
    if(a){
        tmp=dfs(a-1,b,c,d);
        _max=max(_max,tmp);
    }
    if(b){
        tmp=dfs(a,b-1,c,d);
        _max=max(_max,tmp);
    }
    if(c){
        tmp=dfs(a,b,c-1,d);
        _max=max(_max,tmp);
    }
    if(d){
        tmp=dfs(a,b,c,d-1);
        _max=max(_max,tmp);
    }
    return dp[a][b][c][d]=_max+s[all];
}
int main(){
    int n,m,i,j,num[5]={0},x;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
        scanf("%d",&s[i]);
    for(i=0;i<m;i++){
        scanf("%d",&x);
        num[x]++;
    }
    printf("%d\n",s[0]+dfs(num[1],num[2],num[3],num[4]));
}