P1541 题解

ikunTLE · 2025-01-07 20:24:33 · 题解

题目传送门

思路

定义 f_{a,b,c,d} 为用 a 张第 1 种卡片，b 张第 2 种卡，c 张第 3 种卡，d 张第 4 种卡所能获得的最大分值。定义 t_i 为数字 i 在卡片中出现的次数。由于一张卡片都没用时能获得的最大分值为 w_1，故初始化 f_{0,0,0,0}=w_1。

然后推导转移方程，每一次都会向前要一张牌的得分，故分别找 a-1，b-1，c-1，d-1。然后需要加上第 a+2b+3c+4d+1 个格子的分数。

枚举 a 从 0 到 t_1，b 从 0 到 t_2，c 从 0 到 t_3，d 从 0 到 t_4。转移方程为：

最终答案为 f_{t_1,t_2,t_3,t_4}。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,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 x*f;}
const int N=4e2+10,M=50;
int w[N],d[N],dp[M][M][M][M],a[5];
int main(){
    int n=read(),m=read();
    for(int i=1;i<=n;++i)
        w[i]=read();
    for(int i=1;i<=m;++i)
        ++a[read()];
    dp[0][0][0][0]=w[1];
    for(int _=0;_<=a[1];++_) for(int __=0;__<=a[2];++__) for(int ___=0;___<=a[3];++___) for(int ____=0;____<=a[4];++____){
        if(_>0) dp[_][__][___][____]=max(dp[_][__][___][____],dp[_-1][__][___][____]+w[_+__*2+___*3+____*4+1]);
        if(__>0) dp[_][__][___][____]=max(dp[_][__][___][____],dp[_][__-1][___][____]+w[_+__*2+___*3+____*4+1]);
        if(___>0) dp[_][__][___][____]=max(dp[_][__][___][____],dp[_][__][___-1][____]+w[_+__*2+___*3+____*4+1]);
        if(____>0) dp[_][__][___][____]=max(dp[_][__][___][____],dp[_][__][___][____-1]+w[_+__*2+___*3+____*4+1]);
    }
    printf("%d",dp[a[1]][a[2]][a[3]][a[4]]);
    return 0;
}