• [1523] 企鹅的游戏

  • 时间限制: 3000 ms 内存限制: 65535 K
  • 问题描述
  • Shiva养了一只小企鹅。小企鹅很聪明,她总是帮Shiva和他的好朋友想出很多很好玩的游戏。其中有一个游戏特别经典,Shiva和他的小伙伴们百玩不厌。

    游戏规则如下:

    先给出2个正整数序列A1、A2,序列长度分别为L1,L2 (1 ≤ L1, L2 ≤ 2000)。你可以做如下移动:移去第一个序列的最后K1 (K1≥1) 个数(可以是整个序列)并得到它们的和S1,同时移去第二个序列的最后K2 (K2≥1)个数(可以是整个序列)并得到它们的和S2。那么这次移动的费用为 (S1-K1)*(S2-K2)。你可以继续游戏直到两个序列为空。而这次游戏的费用就为每次移动费用的和。

    你现在的目标是使这次游戏的费用最小。

    注意:序列能为空当且仅当两个序列同时为空。

  • 输入
  • 第一行两个正整数L1,L2分别表示两个序列的长度;
    第二行L1个正整数,描述序列A1[1..L1],第i个正整数为A1[i]
    第三行L2个正整数,描述序列A2[1..L2],第i个正整数为A2[i]
    除L1,L2外,所有的整数均不超过100。
  • 输出
  • 一个正整数表示该次游戏的最小费用
  • 样例输入
  • 3 2
    1 2 3
    1 2
    
  • 样例输出
  • 2
  • 提示
  • 来源
  • 本站或者转载
  • 操作

显示春菜