题解 P1912 【[NOI2009]诗人小G】
ww3113306
2018-04-26 14:52:22
第一次写这种二分来优化决策单调性的问题。。。。
调了好久，，，各种细节问题
显然有DP方程：
f[i]=min(f[j] + qpow(abs(sum[i] - sum[j] - L - 1)));
其中f[i]代表到了第i个句子的最小答案
qpow用于处理^p
sum为前缀和
（同时为了处理句子之间的空格问题，我们在统计前缀和的时候就默认在句子后面加一个空格，
然后在计算的时候，由于每一行只有最后一个不用加空格，直接减掉这个多加的空格即可获得正确长度）
首先我们可以打表发现是满足决策单调性的，
即决策是一段一段的
比如这种:
11122224446666
但下面这两种则不满足决策单调性:
11144442222666
11112424
同时这样的决策单调性是很特殊的，即一开始可能是这样的
11111111111111
加入2后：
11122222222222
加入4后：
11122224444444
也就是说就算最终取值是11122224446666，
在中间不断插入的过程中，也是一整段的
因此满足可二分性，
所以我们可以二分来找每个决策管理的区间（即可以转移到的区间）
但是有如下细节需要注意：
**1，区间可能被完整覆盖**
举个栗子，
如果当前状态是
111111111111114
现在加入一个5，那么下一个状态完全有可能是:
111111155555555
因此为了处理这样的情况，我们在二分之前先将会被完整覆盖的区间pop掉
即在插入5前弹出4，
同时这里又要**注意**，这个pop的处理必须在二分之前，
因为在二分过程中，我们需要一个决策来起到check的作用，而这个决策应该是当前插入的x最后应该被放入的那个区间的决策。
这样说可能不太清楚，还是举个栗子
比如当前状态：
111111112222223333
假设下一个状态是
111111112224444444
那么我们二分过程中作为判断依据的那决策就应该是2，
why？
因为观察到3号决策已经被完整的覆盖了，那么我们要对3之前的状态进行check的时候，由于3号不够优（也有可能是受到只能向后转移的限制），我们不能使用3号来check，
但是直接使用2号决策来check，然后在后面2222223333中二分也是不妥的，
因为在3333时，2号并不是最优，
所以为了应对这种情况，
我们先直接判断3333中的第一个3所对应的DP状态，如果插入的x更加优，
那么就代表这个区间是可以被完整的覆盖的，因此我们pop掉这个区间，
依次pop直到不满足条件为止，
这个时候我们就只需要在222222中二分了，于是用2号决策来check就很顺理成章了
**2，新插入的x可能什么区间都覆盖不了，**
也就是说新插入的x可能并不能更新状态，于是我们在二分前做一次特判，
判断当前区间的最后一个是否可以被覆盖,
如果不能，那么这个x无法更新状态，
所以直接continue
---------------以上为计算答案过程--------------
----------------以下为输出部分----------------
因为要输出方案，因此我们在转移时用last数组来记录i是从哪个决策转移而来
又因为不能打乱顺序，所以我们用Next数组来反向记录last数组
比如last中记录的可能是
0 <--- 2 <--- 4
即4由2转移而来，2由转移0而来
那么我们Next数组中记录的就是
0 ---> 2 ---> 4
所以我们从1开始输出，
每当我们到达Next[now]时就输出换行
即输出
1 2
3 4
其实也就是相当于存下了每一行是由哪一句话结尾的，
然后依次输出
最后注意ans可能很大，而且要与1e18比较，所以long long 不够用。
要用 long double
下面是代码（中间有调试输出）
```cpp
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 100100
#define LL long long
#define LD long double
#define ACway 101000
#define inf 1000000000000000000LL
int t,L,p,n;
int s[AC],last[AC],l[AC],r[AC];//对应决策的管理区间
int q[AC],head,tail;//存下当前是哪个决策
int Next[AC];//对last进行相反操作,以便输出
LD f[AC];
LL sum[AC];
char ss[ACway][45];
//bool flag;
/*为什么我感觉就是一个普通DP+决策单调性 ---> 二分,,,,这个不比斜率优化容易理解么？*/
inline LD qpow(LD x)//error!!!x也要用LD！！！
{
LD ans=1;
// printf("x : %lld\n",(LL)(x + 0.5));
int have=p;
while(have)
{
if(have & 1) ans*=x;
x*=x;
have>>=1;
// if(ans > inf || x > inf) flag=true;
}
// printf("ans : %lld\n",(LL)(ans + 0.5));
return ans;
}
inline void pre()
{
scanf("%d%d%d",&n,&L,&p);
for(R i=1;i<=n;i++)
{
scanf("%s",ss[i]+1);
s[i]=strlen(ss[i]+1) + 1;//加上后面的空格
sum[i]=sum[i-1] + s[i];//求出前缀和
}
}
inline LD count(int x,int j)//j --- > x
{
return f[j] + qpow(abs(sum[x] - sum[j] - L - 1));
}
void half(int x)//二分查找
{
int now=q[tail],ll=l[now],rr=n,mid;//因为可能可以覆盖多个区间
while(ll < rr)
{
mid=(ll + rr) >> 1;
if(count(mid,x) < count(mid,now)) rr=mid;//如果更优就往左缩短
else ll=mid + 1;//不然就向右寻找
}
// while(l[q[tail]] >= ll) --tail;//去掉整个都被包含的区间
r[q[tail]]=ll-1;
q[++tail]=x,l[x]=ll,r[x]=n;
/*for(R i=head;i<=tail;i++)
{
for(R j=l[q[i]];j<=r[q[i]];j++)
printf("%d",q[i]);
}
cout << endl;*/
}
inline void getans()
{
head=1,tail=1;
q[1]=0,l[0]=1,r[0]=n;
for(R i=1;i<=n;i++)
{
while(r[q[head]] < i) ++head;//如果当前队首已经取不到了
int now=q[head];
//f[i]=f[now] + qpow(abs(sum[i] - sum[now] - L - 1));
f[i]=count(i,now);//error ??? 用函数的话会爆了会自动转换为inf?
//error!!!是后者转移到前者，所以是now ---> i,要填count(i,now),而不是count(now,i);
// printf("???%d\n",now);
last[i]=now;
if(count(n,q[tail]) < count(n,i)) continue;//如果最后一个都不够优，那就不二分了
while(count(l[q[tail]],q[tail]) > count(l[q[tail]],i)) --tail;//如果当前可以覆盖前面的整个区间
half(i);//注意上面的while要在调用half之前修改，这样取到的now才是正确的
}
}
inline void write()
{
//if(f[n] > inf || flag) puts("Too hard to arrange");
if(f[n] > inf) puts("Too hard to arrange");
else
{
printf("%lld\n",(LL)(f[n] + 0.5));//注意精度误差
for(R i=n ; i ; i=last[i]) Next[last[i]]=i;
int now=0;
for(R i=1;i<=n;i++)
{
now=Next[now];//now先跳了吧
int be=now;//先只到这行结尾，因为for还要加的
for(R j=i; j < be ;j++) printf("%s ",ss[j] + 1);
printf("%s\n",ss[be] + 1);
i=be;//最后再赋i,因为for中还要用到当前i
}
}
puts("--------------------");
}
inline void check()
{
for(R i=1;i<=n;i++)
{
if(r[i] > l[i])
for(R j=l[i];j<=r[i];j++) printf("%d",i);
}
printf("\n");
for(R i=1;i<=n;i++) printf("!!!%lld\n",(LL)(f[i] + 0.5));
cout << endl << endl;
}
inline void work()
{
while(t--)
{
//flag=false;
pre();
getans();
// check();
write();
}
}
int main()
{
freopen("in.in","r",stdin);
scanf("%d",&t);
work();
fclose(stdin);
return 0;
}
```