[bzoj1563][诗人小g]

bzoj1563

思路

首先考虑\(n^2\)的暴力dp,用sum[i]表示前i句话的长度总和。f[i]表示前i句话最小的不协调度之和。转移的时候考虑枚举前面的每个点,找到转移的最优秀的那个点。

然后优化这个暴力。用一个队列存下当前个点之后的点中,哪个区间是从当前点转移更优秀(称为这个点的控制范围)。然后如果当前枚举的位置已经超过队首控制范围。那么队首就可以弹出了。加入新点时,如果队尾控制范围的最左侧也是从当前点转移更优秀,那么队尾就可以弹出了。然后二分当前点与队尾点控制范围的分界点。并且将当前点入队。

代码

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long double ll;
const int N=100000+10;
int read() {
                int x=0, tmp=1;
              char ch=getchar();
           //wxywwwwwwwwwwwwwwwwwwww
         while( (ch<'0') || (ch>'9') ){
        if(ch=='-')tmp=-1; ch=getchar();}
         while( (ch>='0')&&(ch<='9') ){
           x=x*10+ch-'0';ch=getchar();
              }//wxywwwwwwwwwwwwwwww
                return (x*tmp);
}
int n;
ll P,Std;
ll f[N],sum[N];
ll qm(ll x) {//快速幂 
    if(x<0) x=-x;
    ll ans=1;
    int y=P;
    for(ll now=x;y;y>>=1,now=now*now)
        if(y&1) ans*=now;
    return ans;
}
ll calc(int x,int y) {//计算函数 
    return f[y]+qm(sum[x]-sum[y]-Std-1);
}
int find(int l,int r,int x,int y) {//二分从l到r中x比y优秀的第一个位置
    int ans=n;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(calc(mid,x)<calc(mid,y)) ans=mid,r=mid-1;
        else l=mid+1;
     }
     return ans;
 }
  
char s[35];
struct node {
    int xh,l,r;
    node () {
        xh=l=r=0;
    }
    node (int x,int L,int R) {
        xh=x,l=L,r=R;
    }
}q[N];
int main() {
    int T=read();
    while(T--) {
        int head=1,tail=0;
        n=read();Std=read();P=read();   
        for(int i=1;i<=n;++i) {
            scanf("%s",s);
            sum[i]=sum[i-1]+strlen(s)+1;
        }
        q[++tail]=node(0,1,n);
        for(int i=1;i<=n;++i) {
            while(head<=tail&&q[head].r<i) head++;//超出队首控制范围 
            f[i]=calc(i,q[head].xh);
            if(calc(n,i) >calc(n,q[tail].xh)) continue;//如果最后一个点都是从队尾转移优秀,那就不用入队了 
            while(head<=tail&&calc(q[tail].l,i)<calc(q[tail].l,q[tail].xh)) tail--;//将队尾出队 
            q[tail].r=find(q[tail].l,n,i,q[tail].xh)-1;//更改控制范围 
            q[++tail]=node(i,q[tail-1].r+1,n);.//入队 
        }
    
        if(f[n]>1e18) puts("Too hard to arrange");
        else
        printf("%lld\n",(long long)f[n]);
        puts("--------------------");
    }
    
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 13:59
点赞 评论 收藏
分享
程序员小白条:这比例牛逼,750:1
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-21 11:33
昨天是学校最后一场招聘会,鼠鼠去参加了,全场只有一个招聘java的岗位,上来先做一份笔试题,做完后他拿张纸对答案,然后开始问简历上的问题,深圳小厂,6-8k(题目如下),后面还有两轮面试。然后我就在招聘现场逛呀逛,看到有公司招聘电商运营,给的比上年的小厂还多,鼠鼠就去了解了下,然后hr跟鼠鼠要了份简历,虽然我的简历上面全是求职Java开发相关的内容,但是hr还是鼓励我说没关系,她帮我把简历给老板看看,下周一会给我通知。招聘会结束后鼠鼠想了一段时间,也和朋友聊了聊,发现我可能是不太适合这个方向,然后就跟爸爸说回家了给我发条微信,我有些话想跟他说说。晚上爸爸到家了,跟我发了条微信,我立马跑出图书馆跟他打起了电话,这个通话长达一个小时,主要是跟爸爸坦白说我不想找这行了,是你的儿子太没用了,想试试其他行业。然后爸爸也跟我说了很多,说他从来没有希望我毕业后就赚大钱的想法,找不到就回家去,回家了再慢慢找,实在找不到就跟他干(帮别人装修房子,个体户),他也知道工作不好找,让我不要那么焦虑,然后就是聊一些家常琐事。对于后面的求职者呢我有点建议想提一下,就是如果招实习的时间或者秋招开始,而你的简历又很差的情况下,不要说等做好项目填充完简历之后再投,那样就太晚了,建议先把熟悉的项目写上简历,然后边投边面边完善,求职是一个人进步的过程,本来就比别人慢,等到一切都准备好后再投岂不是黄花菜都凉了。时间够的话还是建议敲一遍代码,因为那样能让你加深一下对项目的理解,上面那些说法只是针对时间不够的情况。当然,这些建议可能没啥用,因为我只是一个loser,这些全是建立在我理想的情况下,有没有用还需其他人现身说法。上篇帖子没想到学校被人认了出来,为了不丢脸只能匿名处理了。
KPLACE:找研发类或技术类,主要还是要1.多投 2.多做准备,很多方面都要做准备 3.要有心理准备,投累了就休息一两天,再继续,要相信自己能找到
投递58到家等公司10个岗位
点赞 评论 收藏
分享
给我发了笔试链接,想着等晚上回去做,结果还没做流程就终止了
伟大的小黄鸭在学习:我猜就是笔试几乎没用,就是用来给用人部门拖时间复筛简历的,可能用人部门筛到你简历觉得不合适就提前挂了
投递小鹏汽车等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务