诗人小G 及一类决策单调性问题
常见有决策单调性的函数
1.幂函数（包括 \(\sqrt x\) 之类的东西）
link
提取关键词：“连续”，想到 dp，推出 \(dp_i=dp_j+|pre_i-pre_j+i-j-1-L|^p\)，想到让式子更简单，于是将 \(pre_i\) 加 \(1\)，将 \(L\) 加 \(1\)，\(dp_i=dp_j+|pre_i-pre_j-L|^p\)。请仔细看这个 \(|pre_i-pre_j-L|^p\)，普通的斜率优化肯定不行，考虑决策单调性。可以将 \(pre_i\) 看作 \(X\) 坐标，\(dp_j+|pre_i-pre_j-L|^p\) 看作 \(Y\) 坐标，可以画出一下图像。
- 当 \(P\) 为奇数（图画的不好，请意会）
注意两个函数只有一个交点。这也是能使用以下做法的原因。读者不难看出，在这个点之前，黑线更优，在这个点之后，蓝线更优。满足决策单调性。
2. 当 \(P\) 为偶数（图画的不好，请意会）
注意 \(P\) 为常量，同样的，满足决策单调性。
对于两个函数大小关系转变的临界点，我们可以通过二分找到这个点。记录下来。
和斜率优化的一样的，我们需要在计算当前的 \(dp_i\) 时将临界点 \(
在加入这个点进入队列/栈时，维护决策点单增即可。
#include
#include
#include
#include
#include
#include
#define las que[head]
#define uint unsigned int
#define LL long long
using namespace std;
const int MAXN = 1e6 + 5;
char s[MAXN];
long double dp[MAXN];
int T, n, l, p, a[MAXN], pre[MAXN], que[MAXN], head = 1, tail, f, K[MAXN];
// p 为奇数一定有决策单调性
// 偶数
// dp[i]=dp[j]+|prei-prej-L|^p -> 零点 prej+L 单调递增 也好像有决策单调性？
// just some shit
// 0
void write(LL x) {
if(x < 0) { putchar('-'); x = -x; }
if(x <= 9) { putchar(x + '0'); return; }
write(x / 10); putchar(x % 10 + '0');
}
long double calc(int x, int y) {
long double ans = 1;
for(int i = 1; i <= y; i ++) ans *= x;
return ans;
}
long double Q(int i, int j) {
long double cur = calc(abs(pre[i] - pre[j] - l), p);
return dp[j] + cur;
}
int Half(int i, int j) {
int l = max(i, j), r = n, mid, ans = n + 1;
while(l <= r) {
mid = (l + r) >> 1;
if(Q(mid, j) <= Q(mid, i)) ans = mid, r = mid - 1;
else l = mid + 1;
}
return ans;
}
int main() {
for(scanf("%d", &T); T; T --) {
scanf("%d%d%d", &n, &l, &p); l ++;
for(int i = 1; i <= n; i ++) scanf("%s", s + 1), a[i] = strlen(s + 1), pre[i] = pre[i - 1] + a[i] + 1;
head = 1; tail = 0; que[++ tail] = 0;
for(int i = 1; i <= n; i ++) {
while(head < tail && K[que[head + 1]] <= i) head ++;
dp[i] = dp[las] + calc(abs(pre[i] - pre[las] - l), p);// write(dp[i]); printf("*"); write(calc(abs(pre[i] - pre[las] - l), p)); printf("|");
if(dp[i] <= 1e18) {
while(head < tail && K[que[tail]] >= Half(que[tail], i)) tail --;
K[i] = Half(que[tail], i); que[++ tail] = i;
}
}
if(dp[n] > 1e18) printf("Too hard to arrange\n");
else write((LL)dp[n]), putchar('\n');
printf("--------------------\n");
}
return 0;
}