【BZOJ 1563】 [NOI2009]诗人小G

时间:2021-08-05 06:20:06

Description

【BZOJ 1563】 [NOI2009]诗人小G

Input

【BZOJ 1563】 [NOI2009]诗人小G

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。

 
题解如下
https://www.byvoid.com/blog/noi-2009-poet
我只放AC代码
 #include<cstdio>
#include<cstring>
#define ll long double
struct node{int l,r,p;}q[];
#define MAX 1000000000000000000LL
#define N 100100
ll sum[N],f[N];
int n,l,p,T;
char ch[];
ll pow(ll y){
if(y<)y=-y;
ll ans=;
for (int i=;i<=p;i++) ans*=y;
return ans;
} ll calc(int x,int y){
return f[x]+pow(sum[y]-sum[x]+(y-x-)-l);
} int find(node t,int x){
int l=t.l,r=t.r;
while(l<=r){
int mid=(l+r)>>;
if (calc(x,mid)<=calc(t.p,mid)) r=mid-;
else l=mid+;
}
return l;
} void dp(){
int head=,tail=;
q[++tail]=(node){,n,};
for (int i=;i<=n;i++){
if(q[head].r<i&&head<=tail) head++;
f[i]=calc(q[head].p,i);
if (head>tail||calc(i,n)<=calc(q[tail].p,n)){
while(head<=tail&&calc(q[tail].p,q[tail].l)>=calc(i,q[tail].l)) tail--;
if(head>tail)q[++tail]=(node){i,n,i};
else{
int x=find(q[tail],i);
q[tail].r=x-;
q[++tail]=(node){x,n,i};
}
}
}
} int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&l,&p);
for (int i=;i<=n;i++) scanf("%s",ch),sum[i]=sum[i-]+strlen(ch);
dp();
if(f[n]>MAX)
puts("Too hard to arrange");
else
printf("%lld\n",(long long)f[n]);
puts("--------------------");
}
}

【BZOJ 1563】 [NOI2009]诗人小G的更多相关文章

  1. &lbrack;BZOJ&rsqb; 1563&colon; &lbrack;NOI2009&rsqb;诗人小G

    1D/1D的方程,代价函数是一个p次函数,典型的决策单调性 用单调队列(其实算单调栈)维护决策点,优化转移 复杂度\(O(nlogn)\) #include<iostream> #incl ...

  2. 1563&colon; &lbrack;NOI2009&rsqb;诗人小G

    1563: [NOI2009]诗人小G https://lydsy.com/JudgeOnline/problem.php?id=1563 分析: 直接转移f[i]=f[j]+cost(i,j),co ...

  3. bzoj1563&colon; &lbrack;NOI2009&rsqb;诗人小G 决策单调性&lpar;1D1D&rpar;

    目录 题目链接 题解 代码 题目链接 bzoj1563: [NOI2009]诗人小G 题解 \(n^2\) 的dp长这样 \(f_i = min(f_j + (sum_i - sum_j - 1 - ...

  4. &lbrack;NOI2009&rsqb;诗人小G --- DP &plus; 决策单调性

    [NOI2009]诗人小G 题目描述: 小G是一个出色的诗人,经常作诗自娱自乐. 但是,他一直被一件事情所困扰,那就是诗的排版问题. 一首诗包含了若干个句子,对于一些连续的短句,可以将它们用空格隔开并 ...

  5. P1912 &lbrack;NOI2009&rsqb;诗人小G

    P1912 [NOI2009]诗人小G 思路: 平行四边形不等式优化dp 因为f(j, i) = abs(sum[i]-sum[j]+i-j-1-l)^p 满足平行四边形不等式 j < i f( ...

  6. LG1912 &lbrack;NOI2009&rsqb;诗人小G

    题意 题目描述 小G是一个出色的诗人,经常作诗自娱自乐.但是,他一直被一件事情所困扰,那就是诗的排版问题. 一首诗包含了若干个句子,对于一些连续的短句,可以将它们用空格隔开并放在一行中,注意一行中可以 ...

  7. &lbrack;NOI2009&rsqb; 诗人小G &lbrack;题解&rsqb;

    诗人小G 题目大意 给出 \(n\) 个长度不超过 \(30\) 的句子,要求你对其进行排版. 对于每一行,有一个规定的行标准长度 \(L\) ,每一行的不协调度等于该行的实际长度与行标准长度差的绝对 ...

  8. NOI2009 诗人小G

    Sol 决策单调性+二分 传说中的四边形不等式...其实做了这道题还是不会... 证明简直吃屎//// 贴个传送门这里有部分分做法还有决策单调性的证明 byvoid ISA tell me that ...

  9. 不失一般性和快捷性地判定决策单调(洛谷P1912 &lbrack;NOI2009&rsqb;诗人小G)(动态规划,决策单调性,单调队列)

    洛谷题目传送门 闲话 看完洛谷larryzhong巨佬的题解,蒟蒻一脸懵逼 如果哪年NOI(放心我这样的蒟蒻是去不了的)又来个决策单调性优化DP,那蒟蒻是不是会看都看不出来直接爆\(0\)?! 还是要 ...

随机推荐

  1. MongoDB GridFS 对图片进行增删改

    using MongoDB.Bson; using MongoDB.Driver; using MongoDB.Driver.Builders; using MongoDB.Driver.GridFS ...

  2. Smack Message扩展,添加自定义元素&lpar;标签&rpar;经验分享

    Smack框架对XMPP协议进行了封装,从而方便与Openfire即时通信服务器做交互.说白了,Smack框架可以通过对象构造符合XMPP协议的XML字符串,避免手动拼接字符串. XMPP协议基本XM ...

  3. Mybatis&period;Net 整合 ODP&period;NET Managed

    初步接触MyBatis.Net的朋友,请先移步 MyBatis.Net 学习手记 1. 项目中先添加Oracle.ManagedDataAccess.dll程序集引用 2. MyBatis.Net 中 ...

  4. 第二章实例:ArrayAdapter结合ListView列表视图

    package mydefault.packge; import com.example.codeview.R; import android.app.Activity; import android ...

  5. svn常见问题汇总

    has no ancestry information 经查,由于project/,01Dev/的权限被关闭了,把当前文件夹父目录(project/,01Dev/) 下的 .svn/ 目录删除就好了.

  6. Spring相框:AOP详细说明

    AOP中国的名字叫做面向方面编程.这个名字是很形象.因为你真的可以把像面包切系统.并直接增加面包的修改.科而异,对整个系统,小到一定的方法. AOP它有什么用?有关示例,各组分可以含有安全.事务.,A ...

  7. CG中的数据变量类型

    CG 中的数据变量类型有三: float:高精度浮点值,通常是32位. half:中精度浮点值.通常是16位,范围是-60000至+60000,它适合存储UV坐标,颜色值等. fixed:低精度浮点值 ...

  8. unity 竖屏不能全屏显示

    最近遇到一个问题,硬件显示屏是1080*1920的竖屏,但是导出后打开exe进去并不能全屏 处理办法是1.确认配置都是正确的,简单来说,就是自适应设定,这个网上有很多,就不赘述了. 2.exe启动时需 ...

  9. 万马齐喑究可哀-中文编程的又一波&quot&semi;讨论&quot&semi;

    刚申诉了自动折叠, 还是把回答转帖一下: 吴烜:假设中国人最先开发电脑和设计程序语言,那么各种程序语言会使用汉字吗? 这种有明显倾向性的问题怎么还有市场呢...不管谁先开发的电脑(就不论算盘之类是不是 ...

  10. Delphi中打开网页连接的几种方法

    https://blog.csdn.net/zisongjia/article/details/69398143 正好要用,做个记录.Mark下. 使用了第一种 uses shellapi proce ...