【Tyvj1094】矩形分割

2014-05-26
竞赛题解 / 贪心
TYVJ

描述 Description

出于某些方面的需求，我们要把一块 N×M 的木板切成一个个 1×1 的小方块。

对于一块木板，我们只能从某条横线或者某条竖线（要在方格线上），而且这木板是不均匀的，从不同的线切割下去要花不同的代价。而且，对于一块木板，切割一次以后就被分割成两块，而且不能把这两块木板拼在一起然后一刀切成四块，只能两块分别再进行一次切割。

现在，给出从不同的线切割所要花的代价，求把整块木板分割成 1×1 块小方块所需要耗费的最小代价。

输入格式 InputFormat

输入文件第一行包括 N 和 M，表示长 N 宽 M 的矩阵。
第二行包括 N-1 个非负整数，分别表示沿着 N-1 条横线切割的代价。
第二行包括 M-1 个非负整数，分别表示沿着 M-1 条竖线切割的代价。

输出格式 OutputFormat

输出一个整数，表示最小代价。

样例输入 SampleInput

5 2
6 2 7 5
4

样例输出 SampleOutput

38

数据范围和注释 Hint

对于 60% 的数据，有 1 ≤ N ,M≤ 100；
对于 100% 的数据，有 1 ≤ N,M ≤ 2000。

Tyvj 1094

代码 Code

水。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
struct costs
{
    int s;
    bool h;
}a[10000];
int i,j,t,n,m,l,r,k,z,y,x,ans;
bool comp(costs a,costs b)
{
    return a.s>b.s;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (i=1;i<n;i++) 
    {
        scanf("%d",&a[i].s);
        a[i].h=true;
    }
    for (i=1;i<m;i++) 
    {
        scanf("%d",&a[n+i-1]);
        a[n+i-1].h=false;
    }
    l=1;r=1;
    sort(a+1,a+n+m-1,comp);
    for (i=1;i<n+m-1;i++)
    {
        if (a[i].h) 
        {
            ans+=a[i].s*r;
            l++;
        }
        else
        {
            ans+=a[i].s*l;
            r++;
        }
    }
    printf("%d\n",ans);
    return 0;
}