科普日初中组第二题DP记忆化做法

int dfs(int sum, int i) {
    if (i > m) {  // 处理完所有操作，返回当前总和
        return sum;
    }
    int p = sum;  // 记录当前总和，用于计算收益增量
    int maxn = 0;

    // 分支1：仅可选v[i]+1杯
    if (a[v[i]] == 0 && a[v[i] + 1] > 0) {
        if (dp[i][0] != -1) return sum + dp[i][0];  // 直接返回记忆的增量
        a[v[i] + 1]--;  // 选择v[i]+1杯
        maxn = dfs(sum, i + 1);  // 递归处理下一个操作
        a[v[i] + 1]++;  // 恢复现场，以便后续分支使用
        dp[i][0] = maxn - p;  // 记录当前状态的收益增量
    }
    // 分支2：仅可选v[i]杯
    else if (a[v[i] + 1] == 0 && a[v[i]] > 0) {
        if (dp[i][1] != -1) return sum + dp[i][1];
        a[v[i]]--;
        maxn = dfs(sum, i + 1);
        a[v[i]]++;
        dp[i][1] = maxn - p;
    }
    // 分支3：两杯均不可选，增加sum
    else if (a[v[i]] == 0 && a[v[i] + 1] == 0) {
        if (dp[i][2] != -1) return sum + dp[i][2];
        maxn = dfs(sum + 1, i + 1);  
        dp[i][2] = maxn - p;
    }
    // 分支4：两杯均可选，尝试两种选择取最大值
    else {
        if (dp[i][3] != -1) return sum + dp[i][3];
        // 尝试选择v[i]+1杯
        a[v[i] + 1]--;
        maxn = max(maxn, dfs(sum, i + 1));
        a[v[i] + 1]++;
        // 尝试选择v[i]杯
        a[v[i]]--;
        maxn = max(maxn, dfs(sum, i + 1));
        a[v[i]]++;
        dp[i][3] = maxn - p;
    }
    return maxn;  // 返回当前分支的最大总和
}

#include<bits/stdc++.h>
using namespace std;
int n,m;
int t;
int v[30005],a[30005];
int dp[30005][4];
int dfs(int sum,int i){
	if(i>m){
		return sum;
	}
	int p=sum;
	int maxn=0;
	if(a[v[i]]==0&&a[v[i]+1]){
		if(dp[i][0]!=-1) return sum+dp[i][0];
		a[v[i]+1]--;
		maxn=dfs(sum,i+1);
		a[v[i]+1]++;
		dp[i][0]=maxn-p;
	}
	else if(a[v[i]+1]==0&&a[v[i]]){
		if(dp[i][1]!=-1) return sum+dp[i][1];
		a[v[i]]--;
		maxn=dfs(sum,i+1);
		a[v[i]]++;
		dp[i][1]=maxn-p;
	}
	else if(a[v[i]]==0&&a[v[i]+1]==0){
		if(dp[i][2]!=-1) return sum+dp[i][2];
		maxn=dfs(sum+1,i+1);
		dp[i][2]=maxn-p;
	}
	else{
		if(dp[i][3]!=-1) return sum+dp[i][3];
		a[v[i]+1]--;
		maxn=max(maxn,dfs(sum,i+1));
		a[v[i]+1]++;
		a[v[i]]--;
		maxn=max(maxn,dfs(sum,i+1));
		a[v[i]]++;
		dp[i][3]=maxn-p;
	}
	return maxn;
}
int pd;
int main(){
	//freopen("juice.in","r",stdin);
	//freopen("juice.out","w",stdout);
	cin>>t;
	while(t--){
		memset(dp,-1,sizeof(dp));
		cin>>m>>n;
		pd=1;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		for(int i=1;i<=m;i++){
			cin>>v[i];
		}
		cout<<dfs(0,1)<<'\n';
	}
	return 0;
}