文学类网站模板,软件开发做网站,做net网站,wordpress 代码位置正题
题目链接:https://www.luogu.com.cn/problem/P1912 题目大意
给出nnn个字符串#xff0c;把这些字符串依次用空格#xff08;算一个长度#xff09;连接分成若干段#xff0c;若一段长度为xxx#xff0c;那么代价是∣x−L∣P|x-L|^P∣x−L∣P
求代价和最小的方案把这些字符串依次用空格算一个长度连接分成若干段若一段长度为xxx那么代价是∣x−L∣P|x-L|^P∣x−L∣P
求代价和最小的方案如果代价大于1e181e181e18则输出其他东西
1≤n≤105,1≤L≤3×106,1≤P≤101\leq n\leq 10^5,1\leq L\leq 3\times 10^6,1\leq P\leq 101≤n≤105,1≤L≤3×106,1≤P≤10 解题思路
sis_isi表示前iii个字符串的长度和加iii那么有转移方程 fimin{fj∣si−sj−1−L∣P}f_imin\{f_j|s_i-s_j-1-L|^P\}fimin{fj∣si−sj−1−L∣P} 这个转移很麻烦不能直接用单调队列之类的优化但是它满足四边形不等式 wi,j∣si−sj−1−L∣Pw_{i,j}|s_i-s_j-1-L|^Pwi,j∣si−sj−1−L∣P然后满足 wi,jwi1,j1≤wi,j1wi1,jw_{i,j}w_{i1,j1}\leq w_{i,j1}w_{i1,j}wi,jwi1,j1≤wi,j1wi1,j 这里就不证明了因为证明需要用到求导。
感谢理解的话可以发现因为有个absabsabs所以对于一个决策来说是先下后上而且两个决策最多只有一个交点。
所以有决策单调性我们用单调队列维护一个该决策和它的下一个决策的交换点kik_iki然后每次判断新加入的点与队尾的前一个的交换点是否会代替掉队尾即可。
求交换点的话用二分就好了。
时间复杂度O(Tnlogn)O(Tn\log n)O(Tnlogn)
怕转移太大可以用longdoublelong\ doublelong double存因为如果很大的时候精度就不需要管了我们只需要知道它是否超过1e181e181e18就好了。 code
#includecstdio
#includecstring
#includealgorithm
#includecmath
#define ll long double
using namespace std;
const int N1e510;
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 ans1;while(b){if(b1)ansans*x;xx*x;b1;}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 li,rn;while(lr){int mid(lr)1;if(calc(i,mid)calc(j,mid))lmid1;else rmid-1;}return l;
}
void print(int n){if(!n)return;print(p[n]);for(int ip[n]1;in;i)printf(%s ,st[i]);puts(st[n]);
}
int main()
{scanf(%d,T);while(T--){scanf(%d%d%d,n,L,P);for(int i1;in;i){scanf(%s,st[i]);s[i]s[i-1]strlen(st[i])1;}int head1,tail1;q[1]0;for(int i1;in;i){while(headtailk[head]i)head;f[i]calc(q[head],i);p[i]q[head];while(headtailk[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;
}
