[wikioi]乌龟棋

http://wikioi.com/problem/1068/

多重背包。边界f[0,0,0,0]=a[1]（初始时没有用任何卡片，获得棋盘第一格的分数）
DP方程：f[i,j,k,l]=max(f[i-1,j,k,l],f[i,j-1,k,l],f[i,j,k-1,l],f[i,j,k,l-1])+a[i+j*2+k*3+l*4+1 /*此处+1是必须的，因为初始一格没有用卡片*/ ]
使用了备忘录+递归。

#include <cstdio>
#include <iostream>
#define MAX(a, b) a>b?a:b
using namespace std;

int N;
int M;
int f[45][45][45][45];
int step[355];
int card[5];

void init()     
{     
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &step[i]);
    }
    for (int i = 1; i <= M; i++) {
        int c;
        scanf("%d", &c);
        card[c]++;
    }
    for (int a = 0; a < 45; a++)
        for (int b = 0; b < 45; b++)
            for (int c = 0; c < 45; c++)
                for (int d = 0; d < 45; d++)
                    f[a][b][c][d] = -1;
    f[0][0][0][0] = step[1];
}     

int dp(int a, int b, int c, int d)
{
    if (a < 0 || b < 0 || c < 0 || d < 0) return 0;
    if (f[a][b][c][d] != -1) return f[a][b][c][d];
    int m = dp(a-1, b, c, d);
    m = MAX(m, dp(a, b-1, c, d));
    m = MAX(m, dp(a, b, c-1, d));
    m = MAX(m, dp(a, b, c, d-1));
    m = m + step[1*a+2*b+3*c+4*d+1];
    f[a][b][c][d] = m;
    return m;
}

int main()
{
    init();
    int result = dp(card[1], card[2], card[3], card[4]);
    printf("%d
", result);
    return 0;
}