NOIP2010乌龟棋

题目描述

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。 乌龟棋的棋盘是一行N个格子，每个格子上一个分数（非负整数）。棋盘第1格是唯一 的起点，第N格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

$\dots \dots 12345\dots \dots N$……1 2 3 4 5……N

乌龟棋中M张爬行卡片，分成4种不同的类型（M张卡片中不一定包含所有4种类型 的卡片，见样例），每种类型的卡片上分别标有1、2、3、4四个数字之一，表示使用这种卡 片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择 一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。 游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到 该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的 分数总和。 很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡 片使用顺序使得最终游戏得分最多。 现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到 多少分吗？

输入

输入的每行中两个数之间用一个空格隔开。 第1行2个正整数N和M，分别表示棋盘格子数和爬行卡片数。 第2行N个非负整数， $a_1,a_2\dots \dots a_N$a1​,a2​……aN​

，其中 $a_i$ai​表示棋盘第i个格子上的分数。 第3行M个整数， $b_1,b_2\dots \dots b_M$b1​,b2​……bM​

，表示M张爬行卡片上的数字。 输入数据保证到达终点时刚好用光M张爬行卡片，即
$N-1=\sum b_i$N−1=∑bi​

输出

输出一行一个整数

样例输入

13 8
4 96 10 64 55 13 94 53 5 24 89 8 30
1 1 1 1 1 2 4 1

样例输出

455
提示

【数据范围】

$对于30$对于30%的数据有 $1\le N\le 30，1\le M\le 12$1≤N≤30，1≤M≤12。
$对于50$对于50%的数据有 $1\le N\le 120，1\le M\le 50，且4种爬行卡片，每种卡片的张数不会超过20。$1≤N≤120，1≤M≤50，且4种爬行卡片，每种卡片的张数不会超过20。
$对于100$对于100%的数据有 $1\le N\le 350，1\le M\le 120，且4种爬行卡片，每种卡片的张数不会超过40；$1≤N≤350，1≤M≤120，且4种爬行卡片，每种卡片的张数不会超过40；
$0\le a_i\le 100，1\le i\le N；1\le b_i\le 4，1\le i\le M。输入数据保证N-1=\sum b_i$0≤ai​≤100，1≤i≤N；1≤bi​≤4，1≤i≤M。输入数据保证N−1=∑bi​

分析

最优化问题且具有最优子结构，我们往往考虑动态规划。怎么设计状态呢？所谓状态，就是表示当前的各项指标，各种指标都确定时，这个状态就确定了。设计状态，要把变化的量放进数组中。在这道题中，变化的量就有当前位置，各种牌的使用数，我们发现，知道各种牌的使用数后，当前位置也就确定了，因此不用把当前位置加入状态中。
记 $f\left[a\right]\left[b\right]\left[c\right]\left[d\right]$f[a][b][c][d]表示 $1用了a张，2用了b张，3用了c张，4用了d张$1用了a张，2用了b张，3用了c张，4用了d张的最大值
可以很好得到转移方程：
$f\left[a\right]\left[b\right]\left[c\right]\left[d\right]=max\left(f\right[a-1\left]\right[b\left]\right[c\left]\right[d],f[a\left]\right[b-1\left]\right[c\left]\right[d],f[a\left]\right[b\left]\right[c-1\left]\right[d],f[a\left]\right[b\left]\right[c\left]\right[d-1\left]\right)+v\left[i\right]$f[a][b][c][d]=max(f[a−1][b][c][d],f[a][b−1][c][d],f[a][b][c−1][d],f[a][b][c][d−1])+v[i]

代码如下

//f[a][b][c][d] = max(f[a-1][b][c][d], f[a][b-1][c][d], f[a][b][c-1][d], f[a][b][c][d-1]) + u[i];
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a[355], w[5], f[42][42][42][42];
int main(){
	int i, j, k, t, n, m, v;
	scanf("%d%d", &n, &m);
	for(i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(i = 1; i <= m; i++){
		scanf("%d", &j);
		w[j]++;
	}
	f[0][0][0][0] = a[1];
	for(i = 0; i <= w[1]; i++){
		for(j = 0; j <= w[2]; j++){
			for(k = 0; k <= w[3]; k++){
				for(t = 0; t <= w[4]; t++){
					v = i + j * 2 + k * 3 + t * 4 + 1;
					if(i > 0) f[i][j][k][t] = max(f[i][j][k][t], f[i-1][j][k][t] + a[v]);
					if(j > 0) f[i][j][k][t] = max(f[i][j][k][t], f[i][j-1][k][t] + a[v]);
					if(k > 0) f[i][j][k][t] = max(f[i][j][k][t], f[i][j][k-1][t] + a[v]);
					if(t > 0) f[i][j][k][t] = max(f[i][j][k][t], f[i][j][k][t-1] + a[v]);
				}
			}
		}
	}
	printf("%d", f[w[1]][w[2]][w[3]][w[4]]);
	return 0;
}