竞赛

 

Problem

Source: BSOJ 3643

Description

XX 年 XX 月的某一天,阿狸到黑森林里去玩,不幸被野兽们抓了起来,去觐见动物王国的领袖——巨龙。 动物王国的动物们很不和谐,动不动就会来个决斗,而决斗所破坏掉的森林资源自然全部要国王掏腰包。巨龙知道狐狸是最聪明的【其实是狡猾】,他答应如果阿狸能安排动物们的挑战组合,就答应放了他。

动物们的决斗很有规律,他们分为两个阵营,决斗开始时两个阵营的动物排成两个队,每个动物有一个破坏值,然后由阿狸来安排比赛,动物们会按照顺序分组进行 PK,可以是单挑,群挑,或者是单挑群。具体规则如下:

从后往前,每次从 $A$ 阵营选出连续 $k_1 (k_1 > 0)$ 个动物,他们的破坏值之和为 $s_1$,从 $B$ 阵营选出连续 $k_2 (k_2 > 0)$ 个动物,他们的破坏值之和为 $s_2$,选出的这些动物将进行决斗,这次破坏导致森林的修整费用为 $(s_1 − k_1) \times (s_2 − k_2)$。决斗直到两个队伍都为空时结束。结束之后,这些决斗的总修整费用就为每次 PK 修整费用的和。

阿狸的大脑一片空白,只能让你来完成任务救出阿狸。你需要做的就是使这次决斗的费用最小。

Input

  • 第一行两个正整数 $L_1$,$L_2$ ($1 \leq L_1,L_2 \leq 2000$) 分别表示两阵营的人数;
  • 第二行 $L_1$ 个正整数,描述 $A$ 阵营每个人的破坏值;
  • 第三行 $L_2$ 个正整数,描述 $B$ 阵营每个人的破坏值。

Output

一个正整数,表示森林的最小修整费用。

Sample Input

3 2 
1 2 3 
1 2 

Sample Output

2

 

Solution

注意到破坏值为正数,分开相乘比合起要小。因此选择是 1 对 1,或 1 对多,或多对 1。无论哪种,新增量为 $A(i) \times B(j)$。

Code

Github (C++)

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

const int inf = 0x7fffffff/2;
int n, m;
int a[2005], b[2005], f[2005][2005];

int main() {
    scanf("%d%d",&n, &m);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]), a[i]--;
    for(int i = 1; i <= m; i++) scanf("%d",&b[i]), b[i]--;

    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= m; j++) f[i][j] = inf;

    f[0][0] = 0;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            f[i][j] = min(f[i-1][j-1], min(f[i][j - 1], f[i - 1][j])) + a[i] * b[j];

    printf("%d\n", f[n][m]);

    return 0;
}