很简单的斜率优化题（捂脸）
$$ \text{状态转移方程} \\ f\left( k,n \right) \text{表示在前}n\text{个数中切了}k\text{刀的最优解} \\ \left( \text{对于}n\le k\text{或者}k=\text{0,结果为}0 \right) \\ \text{设}S_n=\sum_{1\le i\le n}{a_i} \\ f\left( k,n \right) =MAX_{1\le i\le n-1}f\left( k-\text{1,}i \right) +\left( S_n-S_i \right) S_i \\ \text{以}k\text{为阶段进行转移} \\ \text{在从}k-\text{1转移到}k\text{时，维护一个单调队列，从队尾到队首的解越来越差} \\ \text{如何构造这个单调队列？} \\ \text{假设单调队列中的所有的元素已经有序，设其中最后的两个元素的}n\text{的取值为}i,j\ \text{设我们要加入到队列的元素的}n\text{的取值为}k \\ \text{设}g\left( x \right) =f\left( k-\text{1,}x \right) -S_{x}^{2} \\ \text{以为单调队列前面的元素比后面的优，所以}i\text{是比}j\text{优的} \\ \text{假如现在}k\text{还比}j\text{优，那么我们显然可以直接把}j\text{扔了，因为它没用} \\ \text{考虑什么时候}k\text{比}j\text{优} \\ \text{如果}i\text{比}j\left( i<j \right) \text{优，那么一定有} \\ f\left( k-\text{1,}i \right) +S_nS_i-S_{i}^{2}>f\left( k-\text{1,}j \right) +S_nS_j-S_{j}^{2} \\ \text{整理一下} \\ f\left( k-\text{1,}i \right) -S_{i}^{2}-\left( f\left( k-\text{1,}j \right) -S_{j}^{2} \right) >S_n\left( S_j-S_i \right) \\ g\left( i \right) -g\left( j \right) >S_n\left( S_j-S_i \right) \\ i<j,\text{所以}S_i<S_j\ \left( S_n\text{单调不降} \right) \\ \text{所以不等式不要变号} \\ \frac{g\left( i \right) -g\left( j \right)}{S_j-S_i}>S_n \\ \text{两边取负} \\ \frac{g\left( i \right) -g\left( j \right)}{S_i-S_j}<-S_n \\ \text{同理，如果}k\text{优于}j\text{，那么我们可以得到} \\ \frac{g\left( k \right) -g\left( j \right)}{S_k-S_j}>-S_n \\ \text{所以我们可以得到，如果}i\text{优于}j\text{而且}k\text{优于}j\left( \text{这个情况应该扔掉}j \right) \ i,j,k\text{应该满足的条件是} \\ \frac{g\left( k \right) -g\left( j \right)}{S_k-S_j}>\frac{g\left( i \right) -g\left( j \right)}{S_i-S_j} \\ \text{即}k,j\text{所构成的直线的斜率大于}i,j\text{所构成的直线的斜率} \\ \text{所以在压入元素}k\text{时，我们需要一直判断直线}ij\text{和直线}jk\text{的斜率关系，如果满足直线}jk\text{的斜率大于直线}ij\text{的斜率，那么我们就需要扔掉点}j \\ \text{一直重复，直到队列中只剩下一个点或者}jk\text{的斜率小于等于}ij\text{的斜率} \\ \text{同时，每个}n\text{的取值在计算时，我们要做的是从队列头取元素} \\ \text{然而}i<j\text{且}i\text{优于}j\text{的条件是} \\ \frac{g\left( i \right) -g\left( j \right)}{S_i-S_j}<-S_n \\ \text{所以我们需要保证队头的元素满足这个关系} \\ \text{所以我们每次考虑队头的两个元素}i,j\text{，如果不满足这个关系，那么就扔掉}i\text{，因为这个时候}i\text{不可能比}j\text{优} \\ \text{然后转移即可} \\ \text{单调队列中的点构成了一个上凸壳，相邻两点所连成的直线，从左到右满足斜率单调不升} \\ \\ $$
#include <iostream>
#include <algorithm>
#include <deque>
#include <cstring>
using int_t = long long int;
using real_t = long double;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 100000;
int_t sum[LARGE + 1];
int n, k;
const real_t EPS = 1e-12;
struct Point
{
//g(pos)
real_t value;
//n的取值
int_t pos;
Point(real_t val = 0, int_t pos = 0)
{
this->value = val;
this->pos = pos;
}
};
real_t scope(const Point &a, const Point &b)
{
if (sum[a.pos] == sum[b.pos])
return (real_t)(a.value - b.value) / EPS;
return (real_t)(a.value - b.value) / (real_t)(sum[a.pos] - sum[b.pos]);
}
int_t dp[201][LARGE + 1];
int_t path[201][LARGE + 1];
Point queue[LARGE * 2 + 1];
int main()
{
scanf("%d%d", &n, &k);
for (int_t i = 1; i <= n; i++)
{
scanf("%lld", &sum[i]);
sum[i] += sum[i - 1];
}
//左闭右开区间
int_t head = 0;
int_t tail = 0;
for (int_t k = 1; k <= ::k; k++)
{
//每次开始时清空队列
head = tail = 0;
//把唯一一个合法的点扔进去
queue[tail] = Point(dp[k - 1][k] - sum[k] * sum[k], k);
tail++;
for (int_t n = k + 1; n <= ::n; n++)
{
/*
g(n)=f(k-1,n)-S(n)^2
*/
//弹出不合法的元素
while (tail - head >= 2 && scope(queue[head], queue[head + 1]) >= -sum[n])
head++;
//写结果
int_t prev = queue[head].pos;
dp[k][n] = dp[k - 1][prev] + (sum[n] - sum[prev]) * sum[prev];
#ifdef DEBUG
cout << "(k=" << k << " n= " << n << ")=" << dp[k][n] << " from (k=" << k - 1 << " n= " << prev << ") = " << dp[k - 1][prev] << endl;
#endif
path[k][n] = prev;
//加入新的元素
Point curr(dp[k - 1][n] - sum[n] * sum[n], n);
while (tail - head >= 2 && (sum[curr.pos] == sum[queue[tail - 1].pos] || scope(curr, queue[tail - 1]) >= scope(queue[tail - 1], queue[tail - 2])))
{
tail--;
}
queue[tail] = curr;
tail++;
}
#ifdef DEBUG
cout << endl;
#endif
}
printf("%lld\n", dp[k][n]);
int_t id = path[k][n];
for (int_t k = ::k; k >= 1; k--)
{
printf("%lld ", id);
id = path[k - 1][id];
}
return 0;
}
发表回复