1010: [HNOI2008] 玩具装箱 toy

Problem Specification Value
Time Limit 1 Sec
Memory Limit 162 MB
Submit 8816
Solved 3510

Description

P 教授要去看奥运, 但是他舍不下他的玩具, 于是他决定把所有的玩具运到北京. 他使用自己的压缩器进行压
缩, 其可以将任意物品变成一堆, 再放到一种特殊的一维容器中. P 教授有编号为 1...... N 的 N 件玩具, 第 i 件玩具经过
压缩后变成一维长度为 Ci. 为了方便整理, P 教授要求在一个一维容器中的玩具编号是连续的. 同时如果一个一维容
器中有多个玩具, 那么两件玩具之间要加入一个单位长度的填充物, 形式地说如果将第 i 件玩具到第 j 个玩具放到一
个容器中, 那么容器的长度将为 x=j-i+Sigma (Ck) i<=K<=j 制作容器的费用与容器的长度有关, 根据教授研究,
如果容器长度为 x, 其制作费用为 (X-L) ^2. 其中 L 是一个常量. P 教授不关心容器的数目, 他可以制作出任意长度的容
器, 甚至超过 L. 但他希望费用最小.

Input

第一行输入两个整数 N, L. 接下来 N 行输入 Ci. 1<=N<=50000, 1<=L, Ci<=10^7

Output

输出最小费用

Sample Input

5 4
3
4
2
1
4

Sample Output

1

HINT

Source

Simple version used to demonstrate the basic principles of writing this problem. There are a few bugs in this version, but it should be either way ignored. This program will not AC, and will TLE.

// Brute force version

#include <iostream>
#include <cstdlib>
#include <cstdio>

#define sqr(x) ((long long)(x) * (long long)(x))
using namespace std;
const int maxn = 50100;
const long long infinit = 0x3f3f3f3f3f3f3f3fll;

int         n, L, C[maxn];
long long   sum[maxn], dp[maxn];

int main()
{
    scanf("%d%d", &n, &L);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &C[i]);
        sum[i] = sum[i - 1] + C[i];
    }
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = infinit;
        for (int j = 0; j < i; j++) {
            long long   diff = sqr(sum[i] - sum[j] + i - j - 1 - L);
            dp[i] = min(dp[i], dp[j] + diff);
        }
    }
    printf("%lld\n", dp[n]);
    return 0;
}
from pydatagen import *
n = randrange(1, 50000)
L = randrange(1, 10000000)
printf('%d %d\n' % (n, L))
for i in range(0, n):
    a = randrange(1, 10000000)
    printf('%d\n' % a)
fclose()