BZOJ_1563_[NOI2009]诗人小G_决策单调性
Description
Input
Output
Sample Input
4 9 3
brysj,
hhrhl.
yqqlm,
gsycl.
4 9 2
brysj,
hhrhl.
yqqlm,
gsycl.
1 1005 6
poet
1 1004 6
poet
Sample Output
--------------------
32
--------------------
Too hard to arrange
--------------------
1000000000000000000
--------------------
【样例说明】
前两组输入数据中每行的实际长度均为6，后两组输入数据每行的实际长度均为4。一个排版方案中每行相邻两个句子之间的空格也算在这行的长度中(可参见样例中第二组数据)。每行末尾没有空格。
HINT
总共10个测试点，数据范围满足：
测试点 T N L P
1 ≤10 ≤18 ≤100 ≤5
2 ≤10 ≤2000 ≤60000 ≤10
3 ≤10 ≤2000 ≤60000 ≤10
4 ≤5 ≤100000 ≤200 ≤10
5 ≤5 ≤100000 ≤200 ≤10
6 ≤5 ≤100000 ≤3000000 2
7 ≤5 ≤100000 ≤3000000 2
8 ≤5 ≤100000 ≤3000000 ≤10
9 ≤5 ≤100000 ≤3000000 ≤10
10 ≤5 ≤100000 ≤3000000 ≤10
所有测试点中均满足句子长度不超过30。
设F[i]表示处理完前i个单词的最小不协调度。s[i]为前缀和+i。L=L+1。
$F[i]=F[j]+(s[i]-s[j]-L)^P$
假设有j1<j2<i1<i2.
j2转移i1比j1转移i1优，j1转移i2比j2转移i2优。
那么$F[j2]+(s[i1]-s[j2]-L)^P\le F[j1]+(s[i1]-s[j1]-L)^P$
$F[j1]+(s[i2]-s[j1]-L)^P\le F[j2]+(s[i2]-s[j2]-L)^P$
那么$(s[i1]-s[j2]-L)^P+(s[i2]-s[j1]-L)^P\le (s[i1]-s[j1]-L)^P+(s[i2]-s[j2]-L)^P$
相当于$(X)^P+(Y)^P\le (X-D)^P+(Y+D)^P$ (D=s[j1]-s[j2])显然不成立。
于是DP满足决策单调性。
用一个单调队列维护区间染色，每次二分即可。
注意答案可能爆longlong，double卡精，直接longdouble没问题，当然也可以double判无解再用longlong输出。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef double f2;
#define N 100050
inline char nc() {
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int rd() {
int x=0; char s=nc();
while(s<'0'||s>'9') s=nc();
while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+s-'0',s=nc();
return x;
}
int rv() {
char s=nc(); int re=0;
while(s<33||s>127) s=nc();
while(s>=33&&s<=127) re++,s=nc();
return re;
}
struct A {
int l,r,p;
}Q[N];
int n,L,P,a[N],from[N],s[N];
f2 f[N];
f2 qp(f2 x,int y) {
f2 re=1; if(x<0) x=-x;
for(;y;y>>=1,x=x*x) if(y&1) re=re*x; return re;
}
ll qpp(ll x,int y) {
ll re=1; if(x<0) x=-x;
for(;y;y>>=1,x=x*x) if(y&1) re=re*x; return re;
}
#define Y(j,i) (f[j]+qp(s[i]-s[j]-L,P))
int find(const A &a,int x) {
int l=a.l,r=a.r+1;
while(l<r) {
int mid=(l+r)>>1;
if(Y(x,mid)>Y(a.p,mid)) l=mid+1;
else r=mid;
}
return l;
}
ll get(int p) {
if(p<n/7) return f[p];
// if(p<700) return f[p];
return get(from[p])+qpp(s[p]-s[from[p]]-L,P);
}
void work() {
n=rd(); L=rd()+1; P=rd();
register int i;
int l,r;
for(i=1;i<=n;i++) {
s[i]=s[i-1]+rv()+1; f[i]=1e20;
}
l=r=0; Q[r++]=(A){0,n,0};
for(i=1;i<=n;i++) {
while(l<r&&Q[l].r<i) l++;
f[i]=Y(Q[l].p,i); from[i]=Q[l].p;
if(Y(i,n)<=Y(Q[r-1].p,n)) {
while(l<r&&Y(i,Q[r-1].l)<=Y(Q[r-1].p,Q[r-1].l)) r--;
if(l==r) Q[r++]=(A){i,n,i};
else {
int x=find(Q[r-1],i);
Q[r-1].r=x-1;
Q[r++]=(A){x,n,i};
}
}
}
if(f[n]>1e18) puts("Too hard to arrange");
else {
printf("%lld\n",get(n));
}
}
int main() {
int T=rd();
while(T--) {
work();
puts("--------------------");
}
}