Solve the brick stacking problem (DP)

Problem description ：

  Ideas 1： First, let's talk about a simple idea , But the complexity is slightly higher .

Define the State f[i][j][k] Show consideration i Items , At this time, put it on the left or on the right or not , At this time, the height of the left border is j, The height on the right is k Whether the state of exists .

In this way, a complete state can be described , The answer is f[n][j][j] In Chinese, it means true, And j maximal .

At this time, the state is transferred

1 Don't put ：f[i][j][k] = f[i - 1][j][k]

2 Put it on the left side. ：f[i][j][k] |= f[i - 1][j - h[i][k]

3 Put it on the right side. ：f[i][j][k] |= f[i - 1][j][k - h[i]

In this way, the current state can be calculated ijk Whether it can be transferred from the previous three states , Because space will explode , So use scrolling and array optimization .

The code is as follows ：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, h[N], m;
bool f[2][N][N];

int main()
{
	cin >> n;
	for(int i = 1; i <= n; i ++ ) cin >> h[i], m += h[i];// Input 
	
	memset(f, false, sizeof f);// initialization , Initialize the illegal status as false
	f[0][0][0] = true;// This is the starting point of the topic 
	
	for(int i = 1; i <= n; i ++ )
	for(int j = 0; j <= m; j ++ )
	for(int k = 0; k <= m; k ++ )
	{
		f[i&1][j][k] = f[(i - 1)&1][j][k];	// State shift 
		if(j - h[i] >= 0) f[i&1][j][k] |= f[(i - 1)&1][j - h[i]][k];
		if(k - h[i] >= 0) f[i&1][j][k] |= f[(i - 1)&1][j][k - h[i]];
	}
	
	int ans = 0;
	for(int j = m; j >= 0; j -- )
	if(f[n&1][j][j])
	{
		ans = j;
		break;
	}
	
	if(ans != 0) cout << ans << endl;
	else cout << "impossible" << endl;
	
	return 0;
}

Ideas 2： If the state is described by height difference , Then there is no need to enumerate two heights , Just enumerate a height difference . So definition f[i][j] Before the election i individual , At this time, the height difference is j The height of the lower tower . Then it needs to be right f The state is max. Yes, place No i Bricks need to be classified and discussed .

1 Don't put ：f[i][j] = f[i - 1][j]

2 Put it on a shorter brick , At this time, the brick is still shorter than the high one .

f[i][j] = f[i - 1][j + h[i]] + h[i]

3 Put it on a shorter brick , At this time, the brick is higher than the high one .

The original height difference ：h[i] - j, So the equation is :f[i][j] = f[i - 1][h[i] - j] + h[i] - j]

4 Put on high bricks

f[i][j] = f[i - 1][j - h[i]] - (j - h[i])

See code for details ：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 500001;

int f[51][N], n, h[51], m;

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++ ) scanf("%d", &h[i]), m += h[i];
	
	memset(f, -1, sizeof f);
	f[0][0] = 0;
	
	for(int i = 1; i <= n; i ++ )
	for(int j = 0; j <= m; j ++ )
	{
		f[i][j] = f[i - 1][j];// Don't put  
		if(j + h[i] <= m && f[i - 1][j + h[i]] != -1) f[i][j] = max(f[i][j], f[i - 1][j + h[i]] + h[i]);// Lower the tower , Shorter than the tall tower  
		if(h[i] - j >= 0 && f[i - 1][h[i] - j] != -1) f[i][j] = max(f[i][j], f[i - 1][h[i] - j] + h[i] - j);// Lower the tower , Higher than the tower  
		if(j - h[i] >= 0 && f[i - 1][j - h[i]] != -1) f[i][j] = max(f[i][j], f[i - 1][j - h[i]]);// Heighten the tower  
	}
	
	if(f[n][0] == 0) puts("-1");
	else cout << f[n][0] << endl;
	
	return 0;
}