首页 > 其他分享 >【题解】P1912 [NOI2009] 诗人小G

【题解】P1912 [NOI2009] 诗人小G

时间:2022-12-31 09:22:05浏览次数:68  
标签:二分 ld int 题解 P1912 转移 maxn sum NOI2009

题意

多测。

给定 \(n\) 个字符串和一个常数 \(L\),试将这些字符串分成若干组,使得:

令 \(len(i)\) 为第 \(i\) 个字符串的长度,则每组字符串的 \(|\sum\limits len(i) - L|\) 的 \(P\) 次方和之和最小。

\(n \leq 10^5, L \leq 3 \times 10^6\),每个字符串的长度不超过 \(30\)

思路

决策单调性优化 dp.

分组问题,考虑决策单调性。大力瞪眼发现成立,证明

状态:\(f[i]\) 表示前 \(i\) 个串的最优解。

转移:令 \(sum[i] = \sum\limits_{j = 1}^i len(i) + 1\),则 \(f[i] = \min\limits_{j = 0}^{i - 1} f[j] + |sum_i - sum_j - L - 1|^P\)

然后考虑用二分队列优化。

用二分队列优化的具体细节是这样的:

性质:从二分队列的队首转移是最优的,并且二分队列中元素的转移范围是递增的。

可以用二分队列优化的方程形如:

\(f[i] = \min f[j] + w(i, j)\),且方程满足决策单调性。

维护二分队列主要是弹出队首、弹出队尾和加入当前元素三部分。

首先,弹出转移范围不包括之后部分的元素。

然后,假设队尾的元素是 \(p\),它的转移范围是 \([l, r]\),当前位置是 \(i\)。如果用 \(i\) 转移 \(l\) 比用 \(p\) 转移 \(l\) 更优,因为一般情况下 \(i\) 的转移范围比 \(p\) 更靠后,所以此后的转移 \(i\) 一定优于 \(p\),故弹出 \(p\).

接下来考虑 \(i\) 的转移范围。因为方程满足决策单调性,所以可以用二分求出用 \(i\) 转移比用队首 \(h\) 转移更优的第一个位置 \(x\),那么 \(i\) 的转移范围是 \([x, n]\)

知道转移范围之后将 \(i\) 加入队尾即可。

注意二分的边界。

时间复杂度 \(O(T n \log n)\)

代码

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef long double ld;

const int maxn = 1e5 + 5;
const int maxl = 35;

int T, n, l, p;
int pre[maxn];
int dq[maxn], lft[maxn];
char s[maxn][maxl];
ld sum[maxn], f[maxn];
bool vis[maxn];

void init()
{
    memset(pre, 0, sizeof(pre));
    memset(vis, false, sizeof(vis));
}

ld qpow(ld base, int power)
{
    ld res = 1;
    while (power)
    {
        if (power & 1) res = res * base;
        base = base * base;
        power >>= 1;
    }
    return res;
}

ld calc(int lst, int cur) { return f[lst] + qpow(abs(sum[cur] - sum[lst] - l - 1), p); }

int query(int p, int q)
{
    int L = max(p, q), R = n;
    while (L < R)
    {
        int mid = (L + R) >> 1;
        if (calc(p, mid) <= calc(q, mid)) R = mid;
        else L = mid + 1;
    }
    if (R == n) return n + (calc(p, n) > calc(q, n));
    return R;
}

int main()
{
    // freopen("P1912_1.in", "r", stdin);
    scanf("%d", &T);
    while (T--)
    {
        init();
        scanf("%d%d%d", &n, &l, &p);
        for (int i = 1; i <= n; i++)
        {
            scanf("%s", s[i]);
            sum[i] = sum[i - 1] + strlen(s[i]) + 1;
        }
        int h, t;
        dq[h = t = 1] = 0;
        for (int i = 1; i <= n; i++)
        {
            while ((h < t) && (lft[h + 1] <= i)) h++;
            f[i] = calc(dq[h], i), pre[i] = dq[h];
            while ((h < t) && (lft[t] >= query(i, dq[t]))) t--;
            dq[++t] = i, lft[t] = query(i, dq[t - 1]);
            // printf("debug %d\n", i);
            // for (int j = h; j <= t; j++) printf("%d ", dq[j].p);
            // putchar('\n');
        }
        if (f[n] > 1e18) puts("Too hard to arrange");
        else
        {
            printf("%lld\n", (ll)f[n]);
            for (int i = n; i; i = pre[i]) vis[i] = true;
            int cur = 1;
            while (cur <= n)
            {
                if (!vis[cur]) printf("%s ", s[cur]);
                else printf("%s\n", s[cur]);
                cur++;
            }
        }
        puts("--------------------");
    }
    return 0;
}

标签:二分,ld,int,题解,P1912,转移,maxn,sum,NOI2009
From: https://www.cnblogs.com/lingspace/p/p1912.html

相关文章

  • 【题解】P3158 [CQOI2011]放棋子
    兄弟们,我起了,一日之计在于晨呐。题意P3158[CQOI2011]放棋子有一个\(n\)行\(m\)列的棋盘和\(c\)种颜色的棋子,每种棋子有\(a_i\)个。要求不同颜色的棋子不能放......
  • HDU 6801 Game on a Circle 题解 (推式子,多项式)
    题目链接首先注意到我们对这个环的扫描是一轮一轮进行的,每轮都会从左到右对每个没被删除的元素以p的概率删除。如果我们能对每个\(t(t\in[0,\infin],t是整数)和i\)求出c......
  • Leetcode面试高频题分类刷题总结及题解(更新中)
    原文链接:Leetcode面试高频题分类刷题总结排序类(Sort)基础知识:快速排序(QuickSort),归并排序(MergeSort)的原理与代码实现。需要能讲明白代码中每一行的目的。快速排序时间......
  • 【题解】P3515 [POI2011]Lightning Conductor(二分栈/分治优化DP)
    [POI2011]LightningConductor题面翻译给定一个长度为\(n\)的序列\(\{a_n\}\),对于每个\(i\in[1,n]\),求出一个最小的非负整数\(p\),使得\(\forallj\in[1,n]\),都......
  • 本博客提供的题解仅供学习,请勿抄袭代码
    近日,发现有部分同学翻取博客上的题解程序复制提交的抄袭行为;在此声明:本博客的代码仅供大家学习参考,对于自身还未学习到对应知识点的同学,请先完善自身基础知识的学习,当且仅......
  • 洛谷P2296 [NOIP2014 提高组] 寻找道路 题解
    题目链接:P2296[NOIP2014提高组]寻找道路-洛谷|计算机科学教育新生态(luogu.com.cn)好了,话不多说上代码:1#include<bits/stdc++.h>2usingnamespacestd;3......
  • Ynoi2019模拟赛题解
    \(Ynoi2019\)模拟赛题解前言:第一次做\(Ynoi\)还是有被离谱到的,我从来没有做到过这么卡常的题目,我到现在\(T1\)都还是\(70\)分,\(lxl\)毒瘤名不虚传啊。但是不得不说,\(Ynoi......
  • 【题解】P1973 [NOI2011] NOI 嘉年华
    yyc学长说是典题,就记一下。题意给出\(n\)个区间,试在丢弃一些区间后,把区间分成两部分,使得不存在同时被两部分中的区间覆盖的位置,求:最终包含区间数较小的部分的区间......
  • 【题解】P1527 [国家集训队]矩阵乘法(整体二分)
    [国家集训队]矩阵乘法题目描述给你一个\(n\timesn\)的矩阵,不用算矩阵乘法,但是每次询问一个子矩形的第\(k\)小数。输入格式第一行有两个整数,分别表示矩阵大小\(n......
  • 恶意竞争题解
    恶意竞争题目大意:巨软和微硬两家公司是竞争对手,微硬希望从巨软公司的软件中找到漏洞来打击竞品的销量。巨软公司的软件有\(s\)个子组件,漏洞分为\(n\)类,微硬公司希望在其......