蓝桥训练之动态规划
- 2021 年 4 月 10 日
- 筆記
入门
数组分组
题意：
一个数组可被分为n组，整个数组的权值被定义为各组内数字之积对1000取模后的总和，求数组的最大权值
思路：
我们用dp[i]表示前i个数分组的最大权值，对于位置i，我们可以枚举最后一个分组的起始位置为j，计算i,j之间的权值，然后更新dp[i]即可。
为了避免过多的计算，我们需要预处理出来每个区间的乘积对1000取模的结果。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 1e3+100, mod = 1000; int n, a[maxn], dp[maxn], pre[maxn][maxn]; int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = 1; i <= n; i++){ pre[i][i] = a[i]; for(int j = i+1; j <= n; j++) pre[i][j] = (pre[i][j-1]*a[j])%mod; } dp[1] = a[1]; for(int i = 2; i <= n; i++){ for(int j = 0; j < i ; j++) dp[i] = max(dp[i], dp[j]+pre[j+1][i]); } printf("%d", dp[n]); }
View Code
墙壁涂色
题意：
一个环形的房间被分成n块，每块的颜色可以为R、G、B，但是相邻两快的颜色必须不同，求涂色的方案数
思路：
这是道递推的题目，用dp[i]表示长度为i的方案数
递推的本质：用已知推未知，寻找前后项之间的关系。仔细观察发现可以分为两种情况，当第1项和第n-1项不同色时，第n项只能取一种颜色；当两者取相同颜色时，第n项可以取两种颜色，于是得到递推表达式：dp[n] = dp[n-1] + 2*dp[n-2]
最后注意初始化的时候需要初始化dp[0]、dp[1]、dp[2](原因稍加思考便知)，并且输出使用long long否则溢出
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define ll long long using namespace std; const int maxn = 1e5+100; ll n, a[maxn], dp[maxn]; int main(){ scanf("%lld", &n); dp[1] = 3, dp[2] = 6, dp[3] = 6; for(int i = 4; i <= n; i++) dp[i] = dp[i-1] + 2*dp[i-2]; printf("%lld", dp[n]); }
View Code
