孙cj实在tcl,蓝桥杯只拿到省二,加练一波区间DP
区间DP
区间DP的模板是类似的,先遍历长度len,再遍历左边界,在左边界循环中确定右边界,在l-r中循环找到每个区间的最优解
题目1:加分二叉树
思路
存下任意从i到j的加分,然后遍历每个点,找到最大值
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 50;
int n;
int w[N];
int f[N][N];
int root[N][N];
void dfs(int l, int r)
{
if (l > r)
return;
// 刚开始为1-n,时根节点
int k = root[l][r];
cout << k << ' ';
// l到根节点左边的根节点
dfs(l, k - 1);
// 根节点右边到r的根节点
dfs(k + 1, r);
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> w[i];
for (int len = 1; len <= n; len ++)
for (int l = 1; l + len - 1 <= n; l ++)
{
int r = l + len - 1;
for (int k = l; k <= r; k ++)
{
// 从l到k-1的加分
int left = k == l ? 1 : f[l][k - 1];
// 从k+1到r的加分
int right = k == r ? 1 : f[k + 1][r];
int score = left * right + w[k];
// 如果l==r,则说明是父节点,加分为自己的值
if (l == r)
score = w[k];
// 若加分比当前的大,则更新,并且记录从l到r的根节点root为k
if (score > f[l][r])
{
f[l][r] = score;
root[l][r] = k;
}
}
}
// 输出1到n的加分
cout << f[1][n] << endl;
dfs(1, n);
}
int main()
{
solve();
}
题目2:能量项链
思路
释放的能量是l-k+k-r,最后得到l-r,所以所有珠子释放完能量后会有l-r的珠子无法释放能量,很明显的区间DP的感觉,这看似是一个环,可以把环拉直处理
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 250;
int n;
int w[N];
int s[N];
int f[N][N];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> w[i];
w[i + n] = w[i];
}
for (int len = 3; len <= n + 1; len ++)
for (int l = 1; l + len - 1 <= n * 2; l ++)
{
int r = l + len - 1;
for (int k = l + 1; k < r; k ++)
{
// f(l,r)表示从l到r最优释放能量,也就是从l到k,再从k到r,再加上l-k-r
f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
}
}
int res = 0;
for (int l = 1; l <= n; l ++)
{
res = max(res, f[l][l + n]);
}
cout << res;
}
int main()
{
solve();
}