[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\n", result);
return 0;
}

  

上一篇:JMETER入门_03_jmeter请求实例


下一篇:open打开窗口并且获得打开窗口的窗口对象