Harmonious dormitory (linear DP / interval DP)

Portal

Solution One （ linear dp）

linear dp

1. State means ：$dp[i][j]surfaceinfrontiZhangdoproductusefalljindividualwoodplateOfmostSmallNoodlesproduct$
2. State shift ：$dp[i][j]=min(dp[k-1][j-1]+(i-k+1)\ast max(H[k,i]))(i\le k\le j)$
   Enumerate the starting position of the last board k,[1, k - 1] use j - 1 A board , [k, i] Use a piece .

Code One

int a[102];// Work height 
int f[102][102];// Interval maximum 
int dp[102][102];

int main()
{
    
	IOS;
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j++)
			for (int k = i; k <= j; k++)
				f[i][j] = max(f[i][j], a[k]);
	
	// State initialization 
	mt(dp, 0x3f);
	for (int i = 0; i <= n; i++)
		dp[i][1] = i * f[1][i];

	for (int i = 1; i <= n; i++)// Stage 
		for (int j = 2; j <= m; j++)// state 
			for (int k = j; k <= i; k++)// Decision making 
				dp[i][j] = min(dp[i][j], dp[k - 1][j - 1] + f[k][i] * (i - k + 1));

	cout << dp[n][m] << endl;

	return 0;
}

Solution Two

Section dp

1. State means ： $dp[l][r][cnt]surfaceinThe\; firstiZhangdoproductToThe\; firstjZhangdoproductusefallcntindividualplateSonOfmostSmallNoodlesproduct$
2. State shift ： $dp[l][r][cnt]=min(dp[l][i][j]+dp[i+1][r][cnt-j])$
   $[l,i]usejindividualplateSon,[i+1][r]usecnt-jindividualplateSon$

Code Two

int a[102];
int f[102][102];
int dp[102][102][102];
int n, m;

int dfs(int l, int r, int cnt)
{
    
	if (l > r || r - l + 1 < cnt) return inf;

	if (cnt == 0) return inf;// There's no board 
	if (cnt == 1) return dp[l][r][1] = f[l][r] * (r - l + 1);
	if (dp[l][r][cnt] != inf) return dp[l][r][cnt];

	for (int i = l; i < r; i++)
		for (int j = 1; j < cnt; j++)
			dp[l][r][cnt] = min(dp[l][r][cnt], dfs(l, i, j) + dfs(i + 1, r, cnt - j));

	return dp[l][r][cnt];
}

int main()
{
    
	IOS;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	mt(dp, 0x3f);
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j++)
			for (int k = i; k <= j; k++)
				f[i][j] = max(f[i][j], a[k]);

	cout << dfs(1, n, m);

	return 0;
}