矩形分割（洛谷 P1324）

矩形分割

题目描述

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

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

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

输入格式

输入文件第一行包括N和M，表示长N宽M的矩阵。

第二行包括N-1个非负整数，分别表示沿着N-1条横线切割的代价。

第三行包括M-1个非负整数，分别表示沿着M-1条竖线切割的代价。

输出格式

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

输入 #1

2 2 3 3

输出 #1

9

这道题思维+贪心；首先我们要知道每次切割用的费用不同，这也意味着我们要先切费用大的那个点。知道了这个，我们还要知道切了一刀后，如果竖着切，那么横着切的点要再切一次，因为分成了两个矩形；横着切同理；一个点只能切一次

代码：

#include<bits/stdc++.h>
using namespace std;
struct Node{
          
   
	int post,date;
}dian[40000];
bool cmp(Node p,Node q){
          
   
	return p.date>q.date;
}
int a[40000];
int main(){
          
   
	int n,m;
	scanf("%d%d",&n,&m);
	int ans=0;
	for(int i=1;i<=n-1;i++){
          
   
		scanf("%d",&dian[++ans].date);
		dian[ans].post=ans;
	}
	for(int i=1;i<=m-1;i++){
          
   
		scanf("%d",&dian[++ans].date);
		dian[ans].post=ans;
	}
	sort(dian+1,dian+1+ans,cmp);
	for(int i=1;i<=ans;i++) a[i]=1;//初始每个点只能切一次
	long long sum=0;
	for(int i=1;i<=ans;i++){
          
   
		if(a[dian[i].post]==0) continue;//已经切过
		sum=sum+(long long)a[dian[i].post]*(long long)dian[i].date;
		a[dian[i].post]=0;
		if(dian[i].post>=n){
          
   
			for(int j=1;j<n;j++){
          
   //长度上的点
				if(a[j]==0) continue;
				a[j]++;
			}
		}
		else{
          
   
			for(int j=n;j<=ans;j++){
          
   //宽度上的点
				if(a[j]==0) continue;
				a[j]++;
			}
		}
	}
	cout<<sum<<endl;
    return 0;
}