企鹅的游戏(penguin)

题目描述

Shiva养了一只小企鹅。小企鹅很聪明，她总是帮Shiva和他的好朋友想出很多很好玩的游戏。其中有一个游戏特别经典，Shiva和他的小伙伴们百玩不厌。游戏规则如下：先给出2个正整数序列A1、A2，序列长度分别为L1，L2 (1 ≤ L1, L2 ≤ 5000)。你可以做如下移动：移去第一个序列的最后P1 (P1≥1) 个数（可以是整个序列）并得到它们的和 S1，同时移去第二个序列的最后P2 (P2≥1)个数（可以是整个序列）并得到它们的和S2。那么这次移动的费用为 (P1-S1)*(P2-S2)。你可以继续游戏直到两个序列为空，所以不允许一个数列空了，而另一个数列中还有数。而这次游戏的费用就为每次移动费用的和。你现在的目标是使这次游戏的费用最小。注意：序列能为空当且仅当两个序列同时为空。

输入

第一行两个正整数L1,L2分别表示两个序列的长度；第二行L1个正整数，描述序列A1[1..L1]，第i个正整数为A1[i] 第三行L2个正整数，描述序列A2[1..L2]，第i个正整数为A2[i] 除L1,L2外，所有的整数均不超过1000。

输出

一个正整数表示该次游戏的最小费用

样例输入

样例输出

提示

对于30%数据，1<=L1,L2<=50

对于60%数据，1<=L1,L2<=500

对于100%数据，1<=L1,L2<=5000

solution

可以发现每次操作k1或者k2一定有一个等于1

（直观的想多个乘一起一定不优）

企鹅的游戏(penguin)-LMLPHP

效率O(n^3)

有个技巧把a[i]--;

f[i][j]=min(f[i][j],f[i-1][j]+a[i]*b[j]);

f[i][j]=min(f[i][j],f[i][j-1]+a[i]*b[j]);

f[i][j]=min(f[i][j],f[i-1][j-1]+a[i]*b[j]);

为什么这样可以呢

假设代价是a*(b+c)

我们可以理解为a*b+a*c

那就相当于b时留着a不删去c时再删去

include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define maxn 2005

using namespace std;

int n,m,f[maxn][maxn],a[maxn],b[maxn];

int main()

{

    cin>>n>>m;

    for(int i=0;i<=n;i++)

    for(int j=0;j<=m;j++)f[i][j]=1e9;

    for(int i=n;i>=1;i--){scanf("%d",&a[i]);a[i]--;}

    for(int i=m;i>=1;i--){scanf("%d",&b[i]);b[i]--;}

    f[0][0]=0;

    for(int i=1;i<=n;i++){

        for(int j=1;j<=m;j++){

            f[i][j]=min(f[i][j],f[i-1][j]+a[i]*b[j]);

            f[i][j]=min(f[i][j],f[i][j-1]+a[i]*b[j]);

            f[i][j]=min(f[i][j],f[i-1][j-1]+a[i]*b[j]);

        }

    }

    cout<<f[n][m]<<endl;

    return 0;

}

l2