[NOIp2010] luogu P1541 乌龟棋

英语老师讲 mind map，真想说一句“声微饭否”。为什么wyy的歌词总是快一点点。在报csp。

题目描述

你在一个序列上向正方向行走，起点是 a[0]a[0]a[0]。每一步可以走 1,2,3,41,2,3,41,2,3,4 格，每种步长的使用次数受限，保证用完步数后恰好到达终点。一次行走的得分为经过所有点的权值之和。求最大得分。

Solution

看这个数据范围就知道是 DP 了。

设 f[i][j][k][l]f[i][j][k][l]f[i][j][k][l] 表示使用 i,j,k,li,j,k,li,j,k,l 次 1,2,3,41,2,3,41,2,3,4 步的最大得分。显然你现在的位置是sum=i+2j+3k+4lsum=i+2j+3k+4lsum=i+2j+3k+4l注意特判起点。时间复杂度 O(M4)O(M^4)O(M4)，空间复杂度 O(M4)O(M^4)O(M4)。

#include<cstdio>

#include<cstdlib>

#include<cstring>

const int MAXN=45;

int n,m;

int g[5]={0,0,0,0,0},a[400];

int sx;

int f[MAXN][MAXN][MAXN][MAXN];

int max(int x,int y){

	return x>y?x:y;

}

int sum(int a,int b,int c,int d){

	return a+b+b+c+c+c+d+d+d+d+1;

}

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;++i)

		scanf("%d",&a[i]);

	for(int i=1;i<=m;++i){

		scanf("%d",&sx);

		++g[sx];

	}

	memset(f,0,sizeof(f));f[0][0][0][0]=a[1];

	for(int i=0;i<=g[1];++i)

		for(int j=0;j<=g[2];++j)

			for(int k=0;k<=g[3];++k)

				for(int l=0;l<=g[4];++l){

					//这里我打得比较丑

					if(i)

						f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[sum(i,j,k,l)]);

					if(j)

						f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[sum(i,j,k,l)]);

					if(k)

						f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[sum(i,j,k,l)]);

					if(l)

						f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[sum(i,j,k,l)]);

				}

	printf("%d",f[g[1]][g[2]][g[3]][g[4]]);

}