整齐打印

5月5日 · 2018年

整齐打印

定义dp[i]表示打印到第[i]个单词的时候,已经产生的空格数的立方最少是多少

那么显然最后的答案就是dp[n]

又由于在计算的过程中,不可避免地要访问形如dp[i-1]的数据

而每次都要检查i-1是不是小于0也是很烦的一件事

注意到dp[0]是不可能的情况,在计算过程中不会遇到

而且事实上当输入的单词个数为0个的时候题目也就失去了实际意义

所以dp[0]自然地可以被当做边界,不需要手动判断了

而第一行之前的累计情况永远是0,这是显然的

那么就可以始终令dp[0]=0,其他dp[i]都为无穷大

状态的转移就变得非常简单

for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= i; k++) 
            dp[i] = std::min(dp[i], dp[k - 1] + extraSpaces(k, i));

现在想要计算打印到第i个单词的时候,最少产生了多少空格的立方

那么就尝试在第1个单词到第i个单词中间加入一个断行,也就是分成1~k-1k~i两段

1~k-1这一段的空格数就是dp[k-1]

k~i这段的就是通过extraSpaces()函数计算的

int ret = M - end + begin;
for (int k = begin; k <= end; ++k) ret -= l[k]; // 根据公式计算空格数
if (ret < 0) return POSITIVE_INFINITY; // 如果放不下,那么就是不合法的组合
if (end == n) return 0; // 最后一行不计入
return ret * ret * ret;

首先根据公式$$M-j+i- \sum_{k=i}^j l_k$$计算空格数

由于这个值不可能为负,为负就说明这么多单词放不下这一行,需要换行,那么这一行放begin到end的情况就是不合法的,返回无穷大

接着,最后一行的空格数是不统计的,那么ret>=0且end==n的时候就返回0(注意最后一行仍旧需要满足ret非负这个条件)

除了这两种特殊情况,其他都是返回ret的立方

但是在第8组测试数据WA

看了好久,才发现立方的范围已经超过int了,要开long long

long long保平安

但是这样是有可能超时的,事实上第9组就超时了

平方的复杂度已经不可能再降了

那就只能减小常系数,那就需要剪枝

for (int k = 1; k <= i; k++)  dp[i] = std::min(dp[i], dp[k - 1] + extraSpaces(k, i));

这一步,应该从i反过来计算到1,然后及时break

这是因为,如果从ki都已经超过了一行的容量

那么k更小的时候,ki的单词数量就会更多,那就更不可能放得下了

所以,k应该从i倒过去到1,并且一旦遇到超过了,就不用继续往下算了

for (int i = 1; i <= n; i++) {
    for (int k = i; k >= 1; k--) {
        long long v = extraSpaces(k, i);
        if (v == POSITIVE_INFINITY) break;
        dp[i] = std::min(dp[i], dp[k - 1] + v);
    }
}

但是这样还是再最后两组数据超时了

原因在于每次根据公式$$M-j+i- \sum_{k=i}^j l_k$$计算空格数

这里其实是多余的

因为前面几个单词计算出来的空格数

到后面一个单词的时候不需要从头开始再算一遍

只要拿到前面一个计算出来的结果,在此基础上加加减减就可以了

记忆化搜索

void calc() {
    for (int from = 1; from <= n; from++) {
        extraSpacesMESCH[from][from] = M - l[from];
        for (int to = from + 1; to <= n; to++) {
            extraSpacesMESCH[from][to] = extraSpacesMESCH[from][to - 1] - l[to] - 1;
        }
    }
}
long long extraSpaces(int begin, int end) {
    long long ret = extraSpacesMESCH[begin][end];
    if (ret < 0) return POSITIVE_INFINITY; 
    if (end == n) return 0; 
    return ret * ret * ret;
}

下面给出完整代码

#include <bits/stdc++.h>

#define MAX_N 10007
#define POSITIVE_INFINITY  0x3F3F3F3F3F3F3F3F

int n, M;
int l[MAX_N] = {0};
int extraSpacesMESCH[MAX_N][MAX_N] = {0};
long long dp[MAX_N] = {0};

long long extraSpaces(int begin, int end) {
//    long long ret = M - end + begin;
//    for (int k = begin; k <= end; ++k) ret -= l[k];
    long long ret = extraSpacesMESCH[begin][end];
    if (ret < 0) return POSITIVE_INFINITY;
    if (end == n) return 0;
    return ret * ret * ret;
}


void calc() {
    for (int from = 1; from <= n; from++) {
        extraSpacesMESCH[from][from] = M - l[from];
        for (int to = from + 1; to <= n; to++) {
            extraSpacesMESCH[from][to] = extraSpacesMESCH[from][to - 1] - l[to] - 1;
        }
    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    scanf("%d%d", &n, &M);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &l[i]);
    for (int i = 1; i <= n; ++i)
        dp[i] = POSITIVE_INFINITY;
    dp[0] = 0;
    calc();
    for (int i = 1; i <= n; i++) {
        for (int k = i; k >= 1; k--) {
//            dp[i] = std::min(dp[i], dp[k - 1] + extraSpaces(k, i));
            long long v = extraSpaces(k, i);
            if (v == POSITIVE_INFINITY) break;
            dp[i] = std::min(dp[i], dp[k - 1] + v);
        }
    }
    printf("%lld\n", dp[n]);
}
0 条回应
验证码
输入运算符及数字使等式成立
{{comment.validate_num1}} = {{comment.validate_num2}}
点赞确定
退出登录?
取消 确定