BZOJ1563 NOI2009 诗人小G

1563: [NOI2009]诗人小G

Time Limit: 100 Sec  Memory Limit: 64 MBSubmit: 2615  Solved: 842[Submit][Status][Discuss]

Description

Input

Output

对于每组数据，若最小的不协调度不超过1018，则第一行一个数表示不协调度若最小的不协调度超过1018，则输出"Too hard to arrange"(不包含引号)。每个输出后面加"--------------------"

Sample Input

4 4 9 3 brysj, hhrhl. yqqlm, gsycl. 4 9 2 brysj, hhrhl. yqqlm, gsycl. 1 1005 6 poet 1 1004 6 poet

Sample Output

108 -------------------- 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。

Source

[ Submit][ Status][ Discuss]

----------------------------

DP+决策单调性

原理和BZOJ1010一样

不过好像不能斜率优化 只会两只log的做法

f[i]=min{f[j]+(s[i]-s[j]-L)^p}

显然最终的决策是形如

000001111122235555

然后就每做完一个点在决策的单调栈内二分出转折点

00000000000000->00000000011111

将后面的所有决策都覆盖成i

但是这题比较毒瘤 p比较大 long long 存不下

所以结果只能用 long double 因为大范围的数据只需要粗略比较即可

原题更加毒瘤 还需要输方案

代码:

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define Rep(i,x,y) for(int i=x;i<y;++i) #define For(i,x,y) for(int i=x;i<=y;++i) using namespace std; const int N = 100005; const long long inf = 1000000000000000001LL; const long long U[]={inf,inf,1e9,1e6,31623,3982,1000,373,178,100,64}; typedef pair<int,int> pii; int T; int n,L,p; long double f[N]; long long s[N]; char str[N][50]; pii q[N]; pii*r=q; pii*l=q; long double pw(long double x,int y){ long double p=1;for(;y;y>>=1,x=x*x)if(y&1){ p=p*x; } return p; } long double trs(int i,int j){ long double t=f[j]+pw(abs(s[i]-s[j]-L),p); return t; } long double F(int i){ pii*it=upper_bound(l,r,make_pair(i,1000000000)); --it; return trs(i,it->second); } void work(){ l=r=q; scanf("%d%d%d",&n,&L,&p);++L; For(i,1,n){ scanf("%s",str[i]); s[i]=strlen(str[i]); } For(i,1,n) s[i]+=s[i-1]; For(i,1,n) s[i]+=i; *(r++)=make_pair(1,0); memset(f,0,sizeof(f)); For(i,1,n){ f[i]=F(i); if(f[i]>=inf){ f[i]=inf; continue; } int L=i+1,R=n+1; while(L<R){ int M=L+R>>1; if(trs(M,i)<=F(M)) R=M; else L=M+1; } pii now=make_pair(L,i); for(;l!=r&&*(r-1)>now;--r); *(r++)=now; } if(f[n]<inf) printf("%lld\n",(long long)f[n]); else puts("Too hard to arrange"); puts("--------------------"); } int main(){ cin>>T; while(T--) work(); return 0; }

 

转载于:https://www.cnblogs.com/rwy233/p/6891528.html