正題

題目鏈接:https://www.luogu.com.cn/problem/P1912

---

題目大意

給出$n$個(gè)字符串，把這些字符串依次用空格（算一個(gè)長(zhǎng)度）連接分成若干段，若一段長(zhǎng)度為$x$，那么代價(jià)是$|x?L{|}^P$

求代價(jià)和最小的方案，如果代價(jià)大于$1e18$則輸出其他東西

$1\le n\le 10^5,1\le L\le 3\times 10^6,1\le P\le 10$

---

解題思路

$s_i$表示前$i$個(gè)字符串的長(zhǎng)度和加$i$，那么有轉(zhuǎn)移方程
$$f_i=min\{f_j+|s_i?s_j?1?L{|}^P\}$$
這個(gè)轉(zhuǎn)移很麻煩不能直接用單調(diào)隊(duì)列之類(lèi)的優(yōu)化，但是它滿(mǎn)足四邊形不等式
$w_{i,j}=|s_i?s_j?1?L{|}^P$，然后滿(mǎn)足
$$w_{i,j}+w_{i+1,j+1}\le w_{i,j+1}+w_{i+1,j}$$
這里就不證明了，因?yàn)樽C明需要用到求導(dǎo)。

感謝理解的話(huà)可以發(fā)現(xiàn)因?yàn)橛袀€(gè)$abs$，所以對(duì)于一個(gè)決策來(lái)說(shuō)是先下后上，而且兩個(gè)決策最多只有一個(gè)交點(diǎn)。

所以有決策單調(diào)性，我們用單調(diào)隊(duì)列維護(hù)一個(gè)該決策和它的下一個(gè)決策的交換點(diǎn)$k_i$，然后每次判斷新加入的點(diǎn)與隊(duì)尾的前一個(gè)的交換點(diǎn)是否會(huì)代替掉隊(duì)尾即可。

求交換點(diǎn)的話(huà)用二分就好了。

時(shí)間復(fù)雜度$O(Tn\log n)$

怕轉(zhuǎn)移太大可以用$longdouble$存，因?yàn)槿绻艽蟮臅r(shí)候精度就不需要管了，我們只需要知道它是否超過(guò)$1e18$就好了。

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define ll long double using namespace std; const int N=1e5+10; int T,n,L,P,p[N],k[N],q[N]; ll f[N],s[N]; char st[N][31]; ll power(ll x,int b){ll ans=1;while(b){if(b&1)ans=ans*x;x=x*x;b>>=1;}return ans; } ll calc(int j,int i) {return f[j]+power(fabs(s[i]-s[j]-1-L),P);} int bound(int i,int j){int l=i,r=n;while(l<=r){int mid=(l+r)>>1;if(calc(i,mid)<calc(j,mid))l=mid+1;else r=mid-1;}return l; } void print(int n){if(!n)return;print(p[n]);for(int i=p[n]+1;i<n;i++)printf("%s ",st[i]);puts(st[n]); } int main() {scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&L,&P);for(int i=1;i<=n;i++){scanf("%s",st[i]);s[i]=s[i-1]+strlen(st[i])+1;}int head=1,tail=1;q[1]=0;for(int i=1;i<=n;i++){while(head<tail&&k[head]<=i)head++;f[i]=calc(q[head],i);p[i]=q[head];while(head<tail&&k[tail-1]>=bound(q[tail],i))tail--;k[tail]=bound(q[tail],i);q[++tail]=i;}if(f[n]>1e18)puts("Too hard to arrange");else printf("%lld\n",(long long)f[n]),print(n);puts("--------------------");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P1912-[NOI2009]诗人小G【四边形不等式,单调队列】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。