【动态规划】洛谷P1877 HAOI2012 音量调节题解

本文主要是介绍【动态规划】洛谷P1877 HAOI2012 音量调节题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、准备材料

题目传送门

二、初步分析

这道题目题意明确，数据范围也只有 $50$ ，可以使用很多方法完成这道题目。

三、深度优先搜索DFS思路

搜索起点为 $b e g in L e v e l$ ，深度 $i = 1$ 。
我们判断当前音量 $p rese n t L e v e l$ 加或减 $c_i$ 是否超过限制（ $\leq presentLevel \plusmn c_i \leq maxLevel$ ），再将深度加 $1$ 往下搜索。当 $\gt n$ 时，记录 $p rese n t L e v e l$ 的最大值，回溯，重复此过程。 $30$ 分。
代码：

#include<bits/stdc++.h>
using namespace std;
int n,beginLevel,maxLevel,ans;
int a[1004];
void dfs(int i,int presentLevel){if(i==n+1){ans=max(ans,presentLevel);return;}if(presentLevel+a[i]<=maxLevel)dfs(i+1,presentLevel+a[i]);if(presentLevel-a[i]>=0)dfs(i+1,presentLevel-a[i]);return;
}
int main(){ans=-1145141919;scanf("%d %d %d",&n,&beginLevel,&maxLevel);for(int i=1;i<=n;i++)scanf("%d",&a[i]);dfs(1,beginLevel);printf("%d",ans);return 0;
}

四、广度优先搜索BFS思路

搜索起点为 $b e g in L e v e l$ ，深度 $i = 1$ 。和一般的BFS一样的思路，不过这种方法BFS队列中要存放两个数据：当前音量 $p rese n t L e v e l$ 和深度 $i$ 。
对于每个队头，我们判断当前音量 $p rese n t L e v e l$ 加或减 $c_i$ 是否超过限制（ $\leq presentLevel \plusmn c_i \leq maxLevel$ ），再将 $\plusmn c_i$ 和 $i + 1$ 入队。当 $\gt n$ 时，记录 $p rese n t L e v e l$ 的最大值，出队。 $30$ 分。
代码：

#include<bits/stdc++.h>
using namespace std;
int n,beginLevel,maxLevel,ans;
int a[1004];
queue<pair<int,int> >q;
void bfs(){int presentLevel,i;q.push({1,beginLevel});while(q.size()){presentLevel=q.front().second;i=q.front().first;q.pop();if(i>n){ans=max(ans,presentLevel);continue;}if(presentLevel+a[i]<=maxLevel)q.push({i+1,presentLevel+a[i]});if(presentLevel-a[i]>=0)q.push({i+1,presentLevel-a[i]});}return;
}
int main(){ans=-1145141919;scanf("%d %d %d",&n,&beginLevel,&maxLevel);for(int i=1;i<=n;i++)scanf("%d",&a[i]);bfs();printf("%d",ans);return 0;
}

五、动态规划DP思路

正解思路。
考虑维护一个 $dp_{n \times maxLevel}$ 的布尔数组， $dp_{i,j}$ 表示执行完前 $i$ 条指令后是否可以达到 $j$ 音量。初始值 $dp_{0,beginLevel}=1$ ，状态转移方程 $dp_{i,j}=dp_{i,j} \lor dp_{i-1,j-c_i} \lor dp_{i-1,j+c_i}$ 。所有指令执行完毕后，从 $ma xL e v e l$ 往下遍历，若 $dp_{n,i}=1$ ，输出 $i$ ，终止程序。若最终程序未被终止，输出 $- 1$ 。 $100$ 分。
代码：

#include<bits/stdc++.h>
using namespace std;
int n,pre,lim,ans;
int a[1004],sum[1004];
int dp[52][1004];
int main(){scanf("%d %d %d",&n,&pre,&lim);for(int i=1;i<=n;i++)scanf("%d",&a[i]);dp[0][pre]=1;for(int i=1;i<=n;i++)for(int ii=lim;ii>=0;ii--){if(ii+a[i]<=lim)dp[i][ii]=dp[i][ii]||dp[i-1][ii+a[i]];if(ii-a[i]>=0)dp[i][ii]=dp[i][ii]||dp[i-1][ii-a[i]];}for(int i=lim;i>0;i--)if(dp[n][i]==1){printf("%d",i);return 0;}printf("-1");return 0;
}