题解:
每一步最多有4种选择,并且题目保证全部卡片用光后一定会正好走到终点,那么我们直接记忆化搜索就可以
dp[i][j][k][l] 表示 当前1,2,3,4卡片还剩i,j,k,l个得到的最大分数。时间复杂度为O(404040*40)
代码:
#include<bits/stdc++.h> #define pb push_back #define SZ(x) ((int)(x).size()) #define all(x) (x).begin(),(x).end() using namespace std; typedef long long ll; typedef vector<int> VI; const int maxn = 1e6 + 4; const int mod = 1e8 + 7; const int inf = 0x3f3f3f3f; const int N = 5005; ll qpow(ll x,ll y){ll ans=1;x%=mod;assert(y>=0);while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;} //ctrl + h ctrl + shift + t //ctrl + shift + d/k //alt + shift + 1/2/3/4 int dp[41][41][41][41],w[maxn],ct[maxn],n,m,d; int dfs(int a,int b,int c,int d,int i) { if(~dp[a][b][c][d]) return dp[a][b][c][d]; int ans=0; if(a) ans=max(ans,dfs(a-1,b,c,d,i+1)); if(b) ans=max(ans,dfs(a,b-1,c,d,i+2)); if(c) ans=max(ans,dfs(a,b,c-1,d,i+3)); if(d) ans=max(ans,dfs(a,b,c,d-1,i+4)); return dp[a][b][c][d]=ans+w[i]; } int main() { //freopen("E:\\S_Code\\input.in","r",stdin); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<=m;i++) scanf("%d",&d),ct[d]++; memset(dp,-1,sizeof dp); printf("%d\n",dfs(ct[1],ct[2],ct[3],ct[4],1)); return 0; }