这题咋做？
当然是爆搜了。
但是蒟蒻不会爆搜（TLE,WA两开花qwq），更不会记忆化搜索，所以我们换个思路。
注意这句话：
这肯定是有用的（洛咕还不会闲圈到给一句毛用都没有的话），那它有什么用呢？
我们再想一想，出牌的顺序与爬行牌的输入顺序没有半毛钱的关系，所以我们完全可以把牌分为4类，统计每种牌的个数。
这样一来，似乎看到了dp的影子。没错我们就是要用四维dp。而且上面的数据保证不会爆空间。
设计状态：dp[i][j][k][o]表示1的牌用i张，2的牌用j张，3的牌用k张，4的牌用o张时的最大得分。
转移方程：dp[i][j][k][o]=max(dp[i][j][k][o],dp[i-1][j][k][o],dp[i][j-1][k][o],dp[i][j][k-1][o],dp[i][j][k][o-1])其中i>0,j>0,k>0,o>0(因为如果等于0，-1后会造成-1下标)
初始状态：dp[0][0][0][0]=fen[1](第一个格子的分数),因为什么牌都不用的时候的初始分数是第一个格子的分数。
最后答案就是所有牌都出完了的分数。
直接上代码
#include<bits/stdc++.h> #define ll long long const ll inf=2147483647; using namespace std; int read() { char ch=getchar(); int x=0;bool f=0; while(ch<'0'||ch>'9') { if(ch=='-')f=1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); } return f?-x:x; } int n,m,fen[359],pai[5];//pai[i]是内容为i的牌的数量,fen[i]是第i个格子的分值 int dp[49][49][49][49]; int main() { n=read();m=read(); for(int i=1;i<=n;i++) fen[i]=read(); for(int i=1;i<=m;i++) pai[read()]++; dp[0][0][0][0]=fen[1]; for(int i=0;i<=pai[1];i++)//注意是要从0开始，因为我们可以不用某种牌 { for(int j=0;j<=pai[2];j++) { for(int k=0;k<=pai[3];k++) { for(int o=0;o<=pai[4];o++) { int r=1+i+2*j+k*3+o*4;//用完牌后，当前的位置 if(i!=0)dp[i][j][k][o]=max(dp[i-1][j][k][o]+fen[r],dp[i][j][k][o]);//zhuyiyaopan0,fouzehuizha if(j!=0)dp[i][j][k][o]=max(dp[i][j-1][k][o]+fen[r],dp[i][j][k][o]); if(k!=0)dp[i][j][k][o]=max(dp[i][j][k-1][o]+fen[r],dp[i][j][k][o]); if(o!=0)dp[i][j][k][o]=max(dp[i][j][k][o-1]+fen[r],dp[i][j][k][o]); } } } } printf("%d",dp[pai[1]][pai[2]][pai[3]][pai[4]]); }