每日一题 乌龟棋 (记忆化搜索)

一.题意

n个格子，1为起点，n为终点
每个格子有一个分数每个格子有一个分数
有 4 种卡片，分别为1，2，3，4，代表能走的步数
走到一点得到该点分数
所有卡片相加恰好到 n 点
求最大能得到的分数

二.题解

四种卡片用完恰好到达终点，而使分数不同的因素是卡片的使用顺序
不难联想到全排列
加上数据比较小
可以考虑用记忆化搜索 表示当前用了 i 张 1 卡, j 张 2 卡, k 张 3 卡, l 张 4 卡的最大得分

三.代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define eps 1e-10
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e5+5;
const int N=5e3+5;
const int mod=1e9+7;

ll w[manx];
ll n,m,a,b,c,d,ans;
ll dp[130][130][130][130];

inline ll dfs(ll i,ll j,ll k,ll l,ll now){
    if(dp[i][j][k][l]) return dp[i][j][k][l];
    ll ans=0;
    if(i<a) ans=max(ans,dfs(i+1,j,k,l,now+1));
    if(j<b) ans=max(ans,dfs(i,j+1,k,l,now+2));
    if(k<c) ans=max(ans,dfs(i,j,k+1,l,now+3));
    if(l<d) ans=max(ans,dfs(i,j,k,l+1,now+4));
    return dp[i][j][k][l]=ans+w[now];
}

int main(){
    io; cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<=m;i++){
        ll x; cin>>x;
        if(x==1) ++a;
        else if(x==2) ++b;
        else if(x==3) ++c;
        else if(x==4) ++d;
    }
    cout<<dfs(0,0,0,0,1)<<endl;
    return 0;
}