题目链接
洛谷P1912【原题，需输出方案】
BZOJ1563【无SPJ，只需输出结果】
题解
四边形不等式
什么是四边形不等式？
一个定义域在整数上的函数(val(i,j))，满足对(forall a le b le c le d)有
那么我们称函数(val(i,j))满足四边形不等式
一般地，当我们需要证明一个函数(val(i,j))满足四边形不等式时，只需证对于(forall j < i)有
因为若该条件满足，
那么有
对于(j < i)有
对于(j + 1 < i)有
两式相加
同理，只要满足第一个条件，对于(forall j + x < i + y)都能推出
所以对(forall a le b le c le d)有
证毕
如何使用四边形不等式优化(dp)？
如果我们有这样一个递推式
如果是(1D1D)方程，自然可以单调队列或者斜率优化
但是如果(val(i,j))比较复杂，无法展开，我们不能有效地分离(i,j)变量，斜率优化就失效了
这个时候就要考虑(val(j,i))是否满足四边形不等式
假使(val(j,i))是满足的
那么我们对(f[i])求出了一个最优转移位置，即为(p[i])
那么对于(forall j < p[i])，都有
我们现在要求(f[k])，其中(k > i)
以上我们有(j < p[i] < i < k)
那么由四边形不等式：
交换一下
与(f[p[i]] + val(p[i],i) le f[j] + val(j,i))相加
得
得证(f[k])的决策(p[k] ge p[i])
换言之，(f[i])的决策满足决策单调性
对于(forall i > j)都有(p[i] ge p[j])
我们就可以从这里入手优化这个(O(n^2))的转移
为求出(f[i])，我们只需求出(p[i])数组
一开始令(p[i] = 0)，即未开始转移前所有位置的最优决策为位置(0)
之后从小枚举(i)
枚举到(i)时，(i)处最优决策更新完毕，那么(forall j le i)，(p[j])和(f[j])都已经计算
为了更新(p[i])数组，我们只需找到(i)所能更新的最左的位置(l)，由于决策的单调性，([l,n])的决策都将更新为(i)
此时二分判断即可
由于需要进行区间赋值，我们可以用一个队列来优化以上操作
具体地，储存若干三元组((pos,l,r))，表示区间([l,r])的决策为(pos)，每次更新从队尾逐个取出检查即可
复杂度优化为(O(nlogn))
诗人小G
设(f[i])为前(i)个句子排版的最小不和谐度
记(len[i])为句子(i)的长度，(sum[i])为句子长度前缀和
容易写出转移方程
我们记(val(j,i) = |(sum[i] - sum[j]) + (i - j - 1) - L|^{P})，显然无法进行斜率优化
考虑(val(j,i))是否满足四边形不等式，即(f[i])的决策是否具有单调性
我们可以打表证明
要证(val(j,i))满足四边形不等式，只需证对(forall j < i)
即证
观察(val(j,i) = |(sum[i] + i) - (sum[j] + j) - (L + 1)|^{P})
我们令(x = (sum[i] + i) - (sum[j] + j) - (L + 1))
我们令(y = (sum[i] + i) - (sum[j + 1] + j + 1) - (L + 1))
那么原式化为：
又因为(x > y)
我们只需证对于函数(f(x) = |x|^{P} - |x + c|^{P})关于(x)单调递减，其中(c)为大于(0)的常数
可以使用导数分类讨论得证
于是就可以用四边形不等式优化成(O(nlogn))
不输出方案版：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long double
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
inline void write(LL x){
if (x / 10 >= 1) write(x / 10);
putchar((int)floor(x - floor(x / 10) * 10) + '0');
}
int n,P,L;
LL f[maxn],a[maxn],sum[maxn];
char s[maxn][32];
int head,tail;
struct node{
int j,l,r;
}q[maxn * 3];
LL qpow(LL a,int b){
LL re = 1;
for (; b; b >>= 1,a = a * a)
if (b & 1) re = re * a;
return re;
}
LL val(int i,int j){
return qpow(fabs(sum[i] - sum[j] + (i - j - 1) - L),P);
}
bool check(int a,int b,int i){
return f[a] + val(i,a) <= f[b] + val(i,b);
}
int main(){
int T = read();
while (T--){
n = read(); L = read(); P = read();
sum[0] = f[0] = 0;
REP(i,n){
scanf("%s",s[i] + 1),a[i] = strlen(s[i] + 1);
sum[i] = sum[i - 1] + a[i];
f[i] = val(i,0);
}
q[head = tail = 0] = (node){0,1,n};
node u; int l,r,mid;
for (int i = 1; i <= n; i++){
f[i] = f[q[head].j] + val(i,q[head].j);
q[head].l++;
if (q[head].l > q[head].r) head++;
while (head <= tail){
u = q[tail--];
if (check(i,u.j,u.l)){
if (head > tail){
q[++tail] = (node){i,i + 1,n};
break;
}
}
else if (!check(i,u.j,u.r)){
q[++tail] = u;
if (u.r == n) break;
else{
q[++tail] = (node){i,u.r + 1,n};
break;
}
}
else {
l = u.l; r = u.r;
while (l < r){
mid = l + r >> 1;
if (check(i,u.j,mid)) r = mid;
else l = mid + 1;
}
q[++tail] = (node){u.j,u.l,l - 1};
q[++tail] = (node){i,l,n};
break;
}
}
}
if (f[n] > qpow(10,18)) puts("Too hard to arrange");
else write(f[n]),puts("");
printf("--------------------");
if (T) puts("");
}
return 0;
}
输出方案版
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long double
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
inline void write(LL x){
if (x / 10 >= 1) write(x / 10);
putchar((int)floor(x - floor(x / 10) * 10) + '0');
}
int n,P,L,p[maxn];
LL f[maxn],a[maxn],sum[maxn];
char s[maxn][32];
int head,tail;
struct node{
int j,l,r;
}q[maxn * 3];
LL qpow(LL a,int b){
LL re = 1;
for (; b; b >>= 1,a = a * a)
if (b & 1) re = re * a;
return re;
}
LL val(int i,int j){
return qpow(fabs(sum[i] - sum[j] + (i - j - 1) - L),P);
}
bool check(int a,int b,int i){
return f[a] + val(i,a) <= f[b] + val(i,b);
}
void print(int u){
if (p[u]) print(p[u]);
for (int i = p[u] + 1; i <= u; i++){
printf("%s",s[i] + 1);
putchar(i < u ? ' ' : '
');
}
}
int main(){
int T = read();
while (T--){
n = read(); L = read(); P = read();
sum[0] = f[0] = 0;
REP(i,n){
scanf("%s",s[i] + 1),a[i] = strlen(s[i] + 1);
sum[i] = sum[i - 1] + a[i];
f[i] = val(i,0);
}
q[head = tail = 0] = (node){0,1,n};
node u; int l,r,mid;
for (int i = 1; i <= n; i++){
f[i] = f[q[head].j] + val(i,q[head].j);
p[i] = q[head].j;
q[head].l++;
if (q[head].l > q[head].r) head++;
while (head <= tail){
u = q[tail--];
if (check(i,u.j,u.l)){
if (head > tail){
q[++tail] = (node){i,i + 1,n};
break;
}
}
else if (!check(i,u.j,u.r)){
q[++tail] = u;
if (u.r == n) break;
else{
q[++tail] = (node){i,u.r + 1,n};
break;
}
}
else {
l = u.l; r = u.r;
while (l < r){
mid = l + r >> 1;
if (check(i,u.j,mid)) r = mid;
else l = mid + 1;
}
q[++tail] = (node){u.j,u.l,l - 1};
q[++tail] = (node){i,l,n};
break;
}
}
}
if (f[n] > qpow(10,18)) puts("Too hard to arrange");
else{
write(f[n]),puts("");
print(n);
}
printf("--------------------");
if (T) puts("");
}
return 0;
}