3288 - 竞赛
时间限制 : 1 秒
内存限制 : 128 MB
XX年XX月的某一天，阿狸到黑森林里去玩，不幸被野兽们抓了起来。去觐见动物王国的领袖——巨龙。
动物王国的动物们很不和谐，动不动就会来个决斗，而决斗所破坏掉的森林资源自然全部要国王掏腰包。巨龙知道狐狸是最聪明的【其实是狡猾】，他答应如果阿狸能安排动物们的挑战组合，就答应放了他。
动物们的决斗很有规律，他们分为两个阵营，决斗开始时两个阵营的动物排成两个队，每个动物有一个破坏值，然后由阿狸来安排比赛，动物们会按照顺序分组进行PK，可以是单挑，群挑，或者是单挑群。具体规则如下：
从后往前，每次从A阵营选出连续k1(k1>0)个动物，他们的破坏值之和为S1，从B阵营选出连续k2（k2>0)个动物,他们的破坏值之和为S2,选出的这些动物将进行决斗，这次破坏导致森林的修整费用为 (S1-K1)*(S2-K2)。决斗直到两个队伍都为空时结束。结束之后，这些决斗的总修整费用就为每次PK修整费用的和。
阿狸的大脑一片空白，只能让你来完成任务救出阿狸。你需要做的就是使这次决斗的费用最小。
题目输入
第一行两个正整数L1,L2分别表示两阵营的人数；
第二行L1个正整数，描述A阵营每个人的破坏值。
第三行L2个正整数，描述B阵营每个人的破坏值。
题目输出
一个正整数表示森林的最小修整费用
输入/输出样例
输入格式
3 2 1 2 3 1 2
输出格式
2
C++解答
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int maxn=2010; int n,m; int a[maxn],b[maxn]; int f[maxn][maxn]; int m_min(int,int,int); void dp(); int main() { //freopen("contest.in","r",stdin); //freopen("contest.out","w",stdout); dp(); return 0; } int m_min(int x,int y,int z) { int temp=x; if(temp>y) temp=y; if(temp>z) temp=z; return temp; } void dp() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; a[i]--; } for(int i=1;i<=m;i++) { cin>>b[i]; b[i]--; } memset(f,0x7f,sizeof(f)); f[n+1][m+1]=0; for(int i=n;i>0;i--) for(int j=m;j>0;j--) f[i][j]=m_min(f[i+1][j],f[i][j+1],f[i+1][j+1])+a[i]*b[j]; cout<<f[1][1]<<endl; }