科普日初中组第二题DP记忆化做法
_Manstein_
·
·
题解
前言
在解决本题时，观察到多数题解采用贪心策略。为提供不同的解题思路，本文提出一种结合深度优先搜索与动态规划优化的方法，通过状态记忆避免重复计算，有效提升效率。
思路
核心代码：
```cpp
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; // 返回当前分支的最大总和
}
```
每次到第 $i$ 个杯子有 $4$ 种方案
- 只有第 $i+1$ 杯能选
- 只有第 $i$ 杯能选
- 第 $i$ 杯和第 $i+1$ 杯都不能选， $sum$ 增加 $1$ 。
- 第 $i$ 杯和第 $i+1$ 杯都能选
中途用 $dp$ 记录一下就行
## 赛时代码
```cpp
#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;
}
```