正文索引 [隐藏]

传送门

题面

我的某室友学过素描，墙上有n张他的作品。这些作品都是宽度为1，高度不定的矩形，从左到右排成一排，且底边在同一水平线上。
宿舍评比就要来了，为了及格，我们决定买不多于m块的矩形木板，把这些作品和谐掉。要求木板也从左到右排成一排，且底边与作品的底边在同一水平线上。
在能够把所有作品和谐掉的前提下，我们希望这些木板的面积和最小，问最小面积和。

输入

第一行两个数n和m，表示作品数和木板数；
第二行n个数Hi，表示从左到右第i个作品的高度。

输出

一行一个数ans表示答案。

样例数据

样例输入
5 2
4 2 3 5 4 
样例输出
22

数据规模

对于30%的数据：1<=n，m<=10；
对于100%的数据：1<=n，m<=100，1<=Hi<=10000。

思路

题面意思转述一下就是：将若干幅矩形的画作通过不同的相邻组合方式，在用尽m块木板的情况下，使得覆盖它们的面积最小。显然这个面积由被覆盖区间中最高的画作来决定，所以需要设hmax[i][j]为hi~hj中画的最大高度。

设 dp[i][j]为用j块板子覆盖前i幅画的最小面积，记k为在dp[i][j]状态下还剩的板子数量。可以得到状态转移方程：

关于初始状态的确定，这里在求最小值，所以dp初始化为INF。如果用一块板子来覆盖前i幅画，显然面积只能为i·hmax[1][i]，所以dp[i][1]初始化为 i·hmax[1][i] 。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define get(x) scanf("%d", &x)
#define lget(x) scanf("%lld", &x)
#define set(a, b) memset(a, b, sizeof(a))
#define rep(a, b, c) for(int a = b; a <= c; a++)

using namespace std;

const int INF = 0X7F7F7F7F;
const int LIM = 105;

int n, m;
int h[LIM];
int dp[LIM][LIM];
int hmax[LIM][LIM];

int main()
{
	set(dp, INF);
	get(n); get(m);
	rep(i, 1, n) get(h[i]);
	rep(i, 1, n) rep(j, i, n) 
		hmax[i][j] = max(h[j], hmax[i][j-1]);
	
	rep(i, 1, n)
	{
		dp[i][1] = i * hmax[1][i];
		rep(j, 2, m) rep(k, 1, i-j+1)
			dp[i][j] = min(dp[i][j], dp[i-k][j-1] + k * hmax[i-k+1][i]);
	}
	
	cout << dp[n][m];
	return 0;
}