题面
我的某室友学过素描,墙上有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; }
评论
还没有任何评论,你来说两句吧!