NOIP拔高组2010 乌龟棋很好的题目

NOIP提高组2010 乌龟棋很好的题目

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。

乌龟棋的棋盘是一行 N个格子，每个格子上一个分数（非负整数）。棋盘第 1 格是唯一的起点，第 N格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

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

Input

第 1 行2 个正整数 N和 M，分别表示棋盘格子数和爬行卡片数。
第 2 行 N个非负整数，a1, a2, ……, aN，其中 ai 表示棋盘第 i 个格子上的分数。
第 3 行M 个整数，b1,b2, ……, bM，表示 M 张爬行卡片上的数字。
输入数据保证到达终点时刚好用光 M 张爬行卡片，即 N−1=∑b_i (1≤i≤m)

Output

输出只有 1行，1 个整数，表示小明最多能得到的分数。
1 ≤ N≤ 350，1 ≤M≤ 120，且 4 种爬行卡片，每种卡片的张数不会超过 40；0 ≤ ai ≤ 100，1 ≤ i ≤ N；1 ≤ bi ≤ 4，1 ≤ i ≤M。输入数据保证 N−1=∑b_i (1≤i≤m)

Sample Input

9 5

6 10 14 2 8 8 18 5 17

1 3 1 2 1

Sample Output

Hint

小明使用爬行卡片顺序为 1，1，3，1，2，得到的分数为 6+10+14+8+18+17=73。注意，由于起点是 1，所以自动获得第 1 格的分数 6。

提交地址：

https://vijos.org/p/1775

下面代码来之 jiangzh7

思路：

显然这是一道动规的题目，状态设计可以用四维f[a][b][c][d]来维护，表示f["1"的张数]["2"的张数]["3"的张数]["4"的张数]

方程就很显然了

　　　　　　f[a][b][c][d]=max{(a>0) f[a-1][b][c][d]+a[a*1+b*2+c*3+d*4],

　　　　　　　　　　　　　　　 (b>0) f[a][b-1][c][d]+a[a*1+b*2+c*3+d*4],

　　　　　　　　　　　　　　　 (c>0) f[a][b][c-1][d]+a[a*1+b*2+c*3+d*4],

　　　　　　　　　　　　　　　 (d>0) f[a][b][c][d-1]+a[a*1+b*2+c*3+d*4]}

当然，由于第一个点自动得分，所以f[0][0][0][0]=a[1]（这也是为什么我们只用计算每一部终点的得分，可以确保起点已经计算）

/*
C++ Code
http://blog.****.net/jiangzh7
*/
#include<cstdio>
#define MAXN 400

int n,m,a[MAXN],sum[5];
int f[50][50][50][50];

int main()
{
    freopen("tortoise.in","r",stdin);
    freopen("tortoise.out","w",stdout);
    scanf("%d%d",&n,&m);
    int i,j,k,t,x;
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    for(i=1;i<=m;i++) {scanf("%d",&x);sum[x]++;}
    f[0][0][0][0]=a[1];
    for(i=0;i<=sum[1];i++)
        for(j=0;j<=sum[2];j++)
            for(k=0;k<=sum[3];k++)
                for(t=0;t<=sum[4];t++)
                {
                    if(i>=1)f[i][j][k][t]>?=f[i-1][j][k][t]+a[1+i*1+j*2+k*3+t*4];
                    if(j>=1)f[i][j][k][t]>?=f[i][j-1][k][t]+a[1+i*1+j*2+k*3+t*4];
                    if(k>=1)f[i][j][k][t]>?=f[i][j][k-1][t]+a[1+i*1+j*2+k*3+t*4];
                    if(t>=1)f[i][j][k][t]>?=f[i][j][k][t-1]+a[1+i*1+j*2+k*3+t*4];
                }
    printf("%d",f[sum[1]][sum[2]][sum[3]][sum[4]]);
    return 0;
}

也可以用下面的方法

#include<stdio.h>
#include<string.h>
int step[400],cn[5],f[50][50][50][50];
int mmax(int a,int b,int c,int d)
{
	int mx=0;
	if(mx<a) mx=a;
	if(mx<b) mx=b;
	if(mx<c) mx=c;
	if(mx<d) mx=d;
	return mx;
}
int DFS(int x)
{
	int a1=0;
	int a2=0;
	int a3=0;
	int a4=0;
	if(x==1) return step[1];
	if(x<=0) return 0;
	if(f[cn[1]][cn[2]][cn[3]][cn[4]]) return f[cn[1]][cn[2]][cn[3]][cn[4]];
	if(cn[1]!=0) {cn[1]--;a1=DFS(x-1)+step[x]; cn[1]++;}
    if(cn[2]!=0) {cn[2]--;a2=DFS(x-2)+step[x]; cn[2]++;}
	if(cn[3]!=0) {cn[3]--;a3=DFS(x-3)+step[x]; cn[3]++;}
	if(cn[4]!=0) {cn[4]--;a4=DFS(x-4)+step[x]; cn[4]++;}
	f[cn[1]][cn[2]][cn[3]][cn[4]]=mmax(a1,a2,a3,a4);
	return f[cn[1]][cn[2]][cn[3]][cn[4]];

}
int main()
{
	int n,m,num,i;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		memset(f,0,sizeof(f));
		memset(cn,0,sizeof(cn));
		for(i=1;i<=n;i++)
			scanf("%d",&step[i]);
		for(i=1;i<=m;i++)
		{
			scanf("%d",&num);
			cn[num]++;
		}
		int ans;
		ans=DFS(n);
		printf("%d\n",ans);
	}
	return 0;
}

NOIP拔高组2010 乌龟棋 很好的题目

Input

Output

Sample Input

Sample Output

Hint

相关推荐

NOIP拔高组2010 乌龟棋很好的题目