BZOJ1044: [HAOI2008]木棍分割(dp 单调队列)

题意

题目链接

Sol

比较套路的一个题。

第一问二分答案check一下

第二问设\(f[i][j]\)表示前\(i\)个数,切了\(j\)段的方案数,单调队列优化一下。

转移的时候只需要保证当前段的长度小于最大限度即可。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 50001, mod = 10007;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-')f =- 1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, a[MAXN], sum[MAXN];
int check(int val) {
    int tot = 0, pre = 0;
    for(int i = 1; i <= N; i++) {
        if(sum[i] - sum[pre] > val) {
            if((sum[i - 1] - sum[pre] <= val) && a[i] <= val) tot++, pre = i - 1;
            else return 0;
        }
    }
    return tot <= M;
}
int solve1() {
    int l = 0, r = sum[N], ans;//二分最大长度
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    return printf("%d ", ans), ans;
}
int add(int x, int y) {
    if(x + y < 0) return x + y + mod;
    else return (x + y > mod ? x + y - mod : x + y);
}
int solve2(int mx) {
    static int f[MAXN], g[MAXN], q[MAXN], ans = 0;
    // f[0][0] = 1;
    for(int i = 1; i <= N; i++) g[i] = (sum[i] <= mx);
    for(int j = 1; j <= M; j++) {
        for(int i = 1, h = 1, t = 0, s = 0; i <= N; i++) {
            while(h <= t && (sum[i] - sum[q[h]] > mx)) s = add(s, -g[q[h++]]);
            q[++t] = i;
            f[i] = s; s = add(s, g[i]);
           /* for(int k = i - 1; k >= 1; k--) {
                if(sum[i] - sum[k] <= mx) (f[i][j] += f[k][j - 1]) %= mod;
                else break;
            }*/
        }
        ans = add(ans, f[N]);
        memcpy(g, f, sizeof(g));
    }
    return ans % mod;
}
int main() {
//  freopen("10.in", "r", stdin);
    N = read(); M = read();
    for(int i = 1; i <= N; i++) a[i] = read(), sum[i] = sum[i - 1] + a[i];
    printf("%d", solve2(solve1()));
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大内老A

基于CallContextInitializer的WCF扩展导致的严重问题

WCF是一个具有极高扩展度的分布式通信框架,无论是在信道层(Channel Layer)还是服务模型层(Service Model),我们都可以自定义相关组件通...

2199
来自专栏一个会写诗的程序员的博客

Linux 查看文件夹下面文件大小的命令: $ du -sh ./*

$ du -sh ./* 93M ./AndroidStudioProjects 1.0M ./Applications 153M ./...

832
来自专栏大内老A

WCF中关于可靠会话的BUG!!

对WCF的可靠会话编程有一定了解的人应该知道,我们可以使用 DeliveryRequirementsAttribute 可以指示WCF确认绑定提供服务或客户端实...

19510
来自专栏数据结构与算法

agc001E - BBQ Hard(dp 组合数)

首先,我们可以把\(C_{a_i + b_i + a_j + b_j}^{a_i + a_j}\)看做从\((-a_i, -b_i)\)走到\((a_j, b_...

931
来自专栏大内老A

WCF技术剖析之三十:一个很有用的WCF调用编程技巧[上篇]

在进行基于会话信道的WCF服务调用中,由于受到并发信道数量的限制,我们需要及时的关闭信道;当遇到某些异常,我们需要强行中止(Abort)信道,相关的原理,可以参...

32210
来自专栏java一日一条

Guava - EventBus(事件总线)

Guava在guava-libraries中为我们提供了事件总线EventBus库,它是事件发布订阅模式的实现,让我们能在领域驱动设计(DDD)中以事件的弱引用...

1492
来自专栏数据结构与算法

BZOJ1014: [JSOI2008]火星人prefix(splay 二分 hash)

982
来自专栏大内老A

WCF技术剖析之二十六:如何导出WCF服务的元数据(Metadata)[实现篇]

元数据的导出就是实现从ServiceEndpoint对象向MetadataSet对象转换的过程,在WCF元数据框架体系中,元数据的导出工作由MetadataEx...

2285
来自专栏Android知识点总结

2-SIII-Android数据固化之Xml的Pull解析和存储

1173
来自专栏GreenLeaves

C# 文件读写系列二

读取文件原则上非常简单,但它不是通过FileInfo和DirectoryInfo来完成的,关于FileInfo和DirectoryInfo请参考C# 文件操作系...

3199

扫码关注云+社区

领取腾讯云代金券