BZOJ1563: [NOI2009]诗人小G(决策单调性 前缀和 dp)

题意

题目链接

Sol

很显然的一个dp方程

\(f_i = min(f_j + (sum_i - sum_j - 1 - L)^P)\)

其中\(sum_i = \sum_{j = 1}^i len_j + 1\)

这个东西显然是有决策单调性的。

单调队列优化一下

我好像已经做过三个这种类型的题了,而且转移的时候\(w\)中总是带个幂函数。。interesting

#include<bits/stdc++.h>
#define chmax(a, b) (a = (a > b ? a : b))
#define chmin(a, b) (a = (a < b ? a : b))
#define LL long long
#define LDB long double 
//#define int long long 
using namespace std;
const int MAXN = 1e5 + 10;
inline int read() {
    int x = 0, f = 1; char c = getchar();
    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 T, N, L, P, sum[MAXN], q[MAXN], c[MAXN], pre[MAXN];//c???ߵ?λ?
char str[MAXN][35];
LDB f[MAXN];
LDB fastpow(LDB a, int p) {
    LDB base = 1;
    while(p) {
        if(p & 1) base = base * a; 
        a = a * a; p >>= 1;
    }
    return base;
}
LDB calc(int j, int i) {
    return f[j] + fastpow(abs(sum[i] - sum[j] - L), P);
}
int lower(int x, int y) {//???x????????
    int l = x, r = N + 1, ans = 0;
    while(l <= r) {
        int mid = l + r >> 1;
        if(calc(x, mid) >= calc(y, mid)) r = mid - 1;
        else l = mid + 1;
    }
    return l;
}
void solve() {
    N = read(); L = read() + 1; P = read();
    for(int i = 1; i <= N; i++) {
        scanf("%s", str[i] + 1);
        sum[i] = sum[i - 1] + strlen(str[i] + 1) + 1;
    }
    memset(q, 0, sizeof(q));
    for(int i = 1, h = 2, t = 2; i <= N; i++) {
        while(h < t && c[h] <= i) h++;
        f[i] = calc(q[h], i); pre[i] = q[h];
        while(h < t && c[t - 1] >= lower(q[t], i)) t--;
        c[t] = lower(q[t], i); q[++t] = i;
    }
    if(f[N] > 1e18) {puts("Too hard to arrange\n--------------------"); return;}
    printf("%.0Lf\n", f[N]);
    puts("--------------------");
}
main() {
    for(T = read(); T; T--) solve();
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏懒人开发

(10.6)James Stewart Calculus 5th Edition:Conic Sections in Polar Coordinates

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

cf1064E. Dwarves, Hats and Extrasensory Abilities(二分 交互)

\(n\)次操作,每次你给出一个点的坐标,系统会返回该点的颜色(黑 / 白),程序最后输出一条直线把所有黑点和白点分隔开

2474
来自专栏落影的专栏

GPUImage详细解析

从源码的角度分析、学习GPUImage和OpenGL ES,这是第一篇,介绍GPUImageFilter 和 GPUImageFramebuffer。 Open...

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

洛谷P2761 软件补丁问题(状压DP,SPFA)

1132
来自专栏用户2442861的专栏

Qt 学习之路 2(45):模型

http://www.devbean.net/2013/02/qt-study-road-2-model/

992
来自专栏机器学习从入门到成神

Python3读取深度学习CIFAR-10数据集出现的若干问题解决

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

1352
来自专栏進无尽的文章

动画| 类似Windows的气泡屏保效果

有时候我们在打印一些CG类型的变量是,无法打印,利用UIKIT中的API可以很方便的实现 字符串和CG变量之间的转换。

4012
来自专栏腾讯AlloyTeam的专栏

教你用 webgl 快速创建一个小世界

Webgl的魅力在于可以创造一个自己的3D世界,但相比较canvas2D来说,除了物体的移动旋转变换完全依赖矩阵增加了复杂度,就连生成一个物体都变得很复杂……这...

1.8K0
来自专栏草根专栏

Python数据分析(二): Pandas技巧 (2)

Pandas的第一部分: http://www.cnblogs.com/cgzl/p/7681974.html github地址: https://github...

3066
来自专栏程序人生

那些年,我追过的绘图语言(续)

自从上一篇文章发布后,大家给我推荐了不少绘图工具,比如startUML,rose,TikZ package,flowchart.js,matlab,R等等。感兴...

4015

扫码关注云+社区

领取腾讯云代金券