histcat

Problem#

The chessboard of Turtle Chess consists of a row of $N$ squares, each square has a score (non-negative integer). The first square is the only starting point, and the $N$-th square is the endpoint. The game requires players to control a turtle piece to move from the starting point to the endpoint.

In Turtle Chess, there are $M$ crawling cards, divided into $4$ different types (not all $4$ types of cards are necessarily included among the $M$ cards, see the example), each type of card is marked with one of the four numbers $1,2,3,4$, indicating that using this card will allow the turtle piece to crawl forward the corresponding number of squares. In the game, players must choose one unused crawling card from all the crawling cards each time to control the turtle piece to move forward the corresponding number of squares, and each card can only be used once.

In the game, the turtle piece automatically gains the score of the starting square, and each time it reaches a square during subsequent crawls, it receives the corresponding score of that square. The player's final game score is the total score of all squares the turtle piece has passed from the starting point to the endpoint.

It is clear that using different sequences of crawling cards will result in different final game scores, and Xiao Ming wants to find a sequence of card usage that maximizes the final game score.

Now, given the scores of each square on the chessboard and all the crawling cards, can you tell Xiao Ming the maximum score he can achieve?

For $100%$ of the data, $1≤N≤350,1≤M≤120$, and there are $4$ types of crawling cards, with no more than $40$ cards of each type; $0≤a_i≤100,1≤i≤N,1≤b_i≤4,1≤i≤M$.

Solution#

Let f[i][j][k][l] be the maximum profit obtained by choosing $i$ cards to move forward $1$ square, $j$ cards to move forward $2$ squares, $k$ cards to move forward $3$ squares, and $l$ cards to move forward $4$ squares.

Just transfer it.

Question#

1. Line 55, add 1.

Code#

#include<bits/stdc++.h>

using namespace std;

const int N = 355;
int a[N], n, m;
int num[5];
int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}
int f[42][42][42][42];


int main()
{
	memset(f, -0x3f, sizeof f);
	n = read(), m = read();
	for(int i = 1;i <= n;i++)
	{
		a[i] = read();
	}

	int t;

	for(int i = 1;i <= m;i++)
	{
		t = read();
		num[t]++;
	}
	f[0][0][0][0] = a[1];
	int ans = -0x7f7f7f7f;
	for(int i = 0;i <= num[1];i++)
	{
		for(int j = 0;j <= num[2];j++)
		{
			for(int k = 0;k <= num[3];k++)
			{
				for(int l = 0;l <= num[4];l++)
				{
					if(i == j && j == k && k == l && i == 0) continue;
					int x = 1 + i + 2 * j + 3 * k + 4 * l;
					if(x > n) continue;
					if(i - 1 >= 0)
						f[i][j][k][l] = max(f[i][j][k][l], f[i - 1][j][k][l] + a[x]);
					if(j - 1 >= 0)
						f[i][j][k][l] = max(f[i][j][k][l], f[i][j - 1][k][l] + a[x]);
					if(k - 1 >= 0)
						f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k - 1][l] + a[x]);
					if(l - 1 >= 0)
						f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k][l - 1] + a[x]);
					ans = max(ans, f[i][j][k][l]);
				}
			}
		}
	}

	printf("%d", ans);

	return 0;
}