[Luogu p1541] tortoise chess [DP]

[NOIP2010 Improvement group ] Tortoise

Background

On Xiao Ming's birthday , Dad gave him a pair of tortoise chess as a gift .

Title Description

The board of tortoise is a line $N$ Lattice , A fraction on each grid （ Non-negative integer ）. Chessboard 1 Lattice is the only starting point , The first $N$ The grid is the end , The game requires the player to control a tortoise piece from the starting point to the end .

In the tortoise game $M$ A crawling card , Divide into 4 Different types （$M$ A card may not contain all of $4$ Types of cards , See Example ）, Each type of card is marked with $1,2,3,4$ One of the four numbers , After using this kind of card , The tortoise pieces will crawl forward with the corresponding number of squares . In the game , Each time the player needs to select a crawling card from all the crawling cards that he has not used before , Control the number of squares that the tortoise moves forward , Each card can only be used once .

In the game , The tortoise chess piece automatically obtains the score of the starting grid , And in the subsequent crawls, every time you reach a grid , You get the corresponding fraction for that lattice . The final game score of the player is the sum of the scores of all the squares that the tortoise pieces have reached from the beginning to the end .

Obviously , Using different crawling cards in different order will make the final game score different , Xiao Ming wants to find a way to use cards in order to get the most points in the game .

Now? , Tell you the score of each grid on the chessboard and all the crawling cards , Can you tell Xiao Ming , How many points can he get at most ？

Input format

Separate two numbers in each line with a space .

The first $1$ That's ok $2$ A positive integer $N,M$, The number of chessboard squares and crawling cards respectively .

The first $2$ That's ok $N$ Nonnegative integers ,$a_1,a_2,\dots ,a_N$, among $a_i$ It means chessboard No $i$ Points on a grid .

The first $3$ That's ok $M$ It's an integer ,$b_1,b_2,\dots ,b_M$, Express M The numbers on a crawling card .

Input data to make sure it's just used up at the end $M$ A crawling card .

Output format

$1$ It's an integer , It means the maximum score Xiao Ming can get .

Examples #1

The sample input #1

9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1

Sample output #1

73

Tips

Every test point $1s$

Xiao Ming uses crawling cards in the order of $1,1,3,1,2$, The score is $6+10+14+8+18+17=73$. Be careful , Because the starting point is $1$, So automatically get the first $1$ The fraction of a lattice $6$.

about $30\%$ Data are available. $1\le N\le 30,1\le M\le 12$.

about $50\%$ Data are available. $1\le N\le 120,1\le M\le 50$, And $4$ Sort of crawling cards , The number of cards of each type will not exceed $20$.

about $100\%$ Data are available. $1\le N\le 350,1\le M\le 120$, And $4$ Sort of crawling cards , The number of cards of each type will not exceed $40$;$0\le a_i\le 100,1\le i\le N,1\le b_i\le 4,1\le i\le M$.
$link$

analysis ：

set up $f_{i,j,k,l}$ Indicates that one step card is used $i$ Time Two steps $j$ And so on
Because there are only $40$ Zhang therefore $O(n^4)$ We can do
So direct transfer

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define reg register
using namespace std;
typedef long long ll;
const int N=355,M=45;
int n,m,val[N],f[M][M][M][M],a,b,c,d;
int main(){
    
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&val[i]);
	for(int i=1,x;i<=m;i++)
	{
    
		scanf("%d",&x);
		if(x==1) a++;
		if(x==2) b++;
		if(x==3) c++;
		if(x==4) d++;
	}
	f[0][0][0][0]=val[1];
	for(int i=0;i<=a;i++)
	for(int j=0;j<=b;j++)
	for(int k=0;k<=c;k++)
	for(int l=0;l<=d;l++)
	{
    
		int step=i+j*2+k*3+l*4+1;
		if(i>0) f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+val[step]);
		if(j>0) f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+val[step]);
		if(k>0) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+val[step]);
		if(l>0) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+val[step]);
	}
	printf("%d",f[a][b][c][d]);
	return 0;
}