比赛 10101115 评测结果 AAAAAAWWWW
题目名称 矩形分割 最终得分 60
用户昵称 lc 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-11-15 11:02:36
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn = 2010,INF = 100000000;
int N,M;
int H[maxn],S[maxn],SH[maxn],SS[maxn];
int F[maxn*2][maxn];


bool cmp(const int a,const int b)
{
	return a >b;
}

void prep()
{
	scanf("%d%d",&N,&M);
	for (int i=1; i<N; i++)
		scanf("%d",&H[i]);
	sort(H+1,H+N,cmp);
	for (int i=1; i<M; i++)
		scanf("%d",&S[i]);
	sort(S+1,S+M,cmp);
	for (int i=N-1; i>=1; i--) SH[i] = SH[i+1] + H[i];
	for (int i=M-1; i>=1; i--) SS[i] = SS[i+1] + S[i];
}

void work()
{
	for (int i=1; i<=N+M-2; i++)
		for (int j=0; j<=i && j<=N-1; j++)
		{
			int temp = INF;
			if (j) temp = min(temp,F[i-1][j-1]+H[j]+SS[i-j+1]);
			if (i>j) temp = min(temp,F[i-1][j]+S[i-j]+SH[j+1]);
			F[i][j] = temp;
		}
	printf("%d\n",F[N+M-2][N-1]);
}


int main()
{
	freopen("cut.in","r",stdin);
	freopen("cut.out","w",stdout);
	prep();
	work();
	return 0;
}