前言
做完然后看看题解是怎么写的,好像都是单调队列优化dp,我的ST优化dp居然能卡过去也是万幸了。
题意:
…有点长,略略略了
做法:
线性dp,f[i][j]代表截止第i个点,锅里一共有j种配料时最大的价值。
转移方程也很简单,从上一层开始转移,因为有拿走s个的限制条件,所以暴力的dp是N^3的复杂度。
考虑优化
f[i][j] = max(f[i][j], f[i - 1][k] + j * a[i]);
能看出只要取出上一层的某个最大值,就不用这样子枚举一遍了。所以我采用ST表优化。
int a[N], f[N][N];
struct ST
{
// 注意下标范围是0开始还是1开始,下面有提示
int f_max[N][13], lg[N];
void init(int a[], int n)
{
lg[0] = -1;
for (int i = 1; i <= n; i++)
{
f_max[i][0] = a[i];
if ((i & (i - 1)) == 0) lg[i] = lg[i - 1] + 1;
else lg[i] = lg[i - 1];
}
// 还有这里
f_max[0][0] = a[0];
int t = lg[n];
for (int j = 1; j <= t; j++)
{
// 这里
for (int i = 0; i <= n - (1ll << j) + 1; i++)
{
f_max[i][j] = max(f_max[i][j - 1], f_max[i + (1ll << (j - 1))][j - 1]);
}
}
}
int que_max(int l, int r)
{
int k = lg[r - l + 1];
if (l == 0 && r > 0)
{
l = 1;
k = lg[r - l + 1];
return max({f_max[0][0], f_max[l][k], f_max[r - (1ll << k) + 1][k]});
}
return max(f_max[l][k], f_max[r - (1ll << k) + 1][k]);
}
} S;
void solve()
{
int n, w, s;
cin >> n >> w >> s;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 0; i <= n; i++)
for (int j = 0; j <= w && j <= i; j++)
f[i][j] = -1e18;
f[0][0] = 0;
S.init(f[0], n);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= w && j <= i; j++)
{
// for (int k = j - 1; k <= w && k - (j - 1) <= s && k <= i - 1; k++)
// {
// f[i][j] = max(f[i][j], f[i - 1][k] + j * a[i]);
// }
// 想办法优化掉这个维度,感觉可以优化
// 从上一层的 j - 1开始,最长到 min(w, j - 1 + s, i - 1), 三个数都是定值啊
f[i][j] = S.que_max(j - 1, min({w, j - 1 + s, i - 1})) + j * a[i];
}
S.init(f[i], min(w, i));
// if (i == 1)
// {
// cout << "====================\n";
// cout << S.que_max(0, 1) << "\n";
// cout << "=============\n";
// }
}
// cout << f[2][1] << "\n";
cout << *max_element(f[n] + 1, f[n] + 1 + w);
}
这题我会写哎