DP problem set

”Strive for greatness"

                                                                                      --2021.8.29

1. Pressure dp:

There is one N*M(N<=5,M<=1000) The chessboard of , Now there is 1*2 And 2*1 There are countless small pieces of wood , To cover the whole chessboard , How many ways ？ The answer only needs mod1,000,000,007 that will do .

Consider storing the state of each row in binary such as 00100 It means the first one 3 OK, there is a box , The core idea of shape pressure

state Represents the status of the current line nex Represents its impact on the next column ( For example, put wooden blocks horizontally )

AC Code :

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int  N = 207, mod = 1e9 + 7;
int dp[N][N];//dp[i][state] Before presentation i-1 Number of options listed 
int n, m;
// Enumerate to i Column  , The first j That's ok   And the first j The state of the line   And its impact on the next column nex
void dfs(int i, int j, int state, int nex)
{
	if (j == n)
	{
		dp[i + 1][nex] += dp[i][state];
		dp[i + 1][nex] %= mod;
		return;
	}
	if ((state) & (1 << j) > 0)// If the row has been occupied by the previous column   Just skip. 
	{
		dfs(i, j + 1, state, nex);
	}
	if ((state) & (1 << j) == 0)// If the line is empty   Just put 1 individual 2*1 Of the lattice  
	{
		dfs(i, j + 1, state, nex | (1 << j));// hold nex Of the j A into 1, Placing it horizontally will affect the next column 
	}
	if ((j + 1) < n && ((state) & (1 << (j + 1))) == 0 && ((state) & (1 << j) == 0))
	{
		dfs(i, j + 2, state, nex);// Skip two lines 
	}
	return;
}
int main()
{
	while (scanf("%d%d", &n, &m) != EOF)
	{
		memset(dp, 0, sizeof(dp));
		if (n == 0 && m == 0) { break; }
		for (int i = 1; i <= m; i++)
		{
			for (int j = 0; j <(1<<n); ++j)
			{
				if (dp[i][j])// If there are schemes , Then it is extended to the next column 
				{
					dfs(i, 0, j, 0);
				}
			}
		}
		printf("lld\n", dp[m + 1][0]);
	}
}

2. subject :Problem - 431C - Codeforces

  The main idea of the topic ： A special kind of tree , Every vertex has k One side , The weights are respectively 1~k, Ask how many can be found, that is, the sum of the weights is n And the sum of the weights of at least one edge is greater than d The number of paths

  Answer key :1.dp[i][0] The sum of the representative weights is i And does not meet the conditions ,dp[i][1] Then the conditions are met

          2. If The weight of the current edge j>=d, The original dp[i-j][0]+dp[i-j][1] Add all the plans

              namely dp[i][1]+=d[i-j][1]+dp[i-j][0]

              otherwise

            dp[i][1]+=dp[i-j][1]

            dp[i][0]+=dp[i-j][0]

         AC Code :

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod = 1e9 + 7;
const int N = 101;
long long  dp[N][2];
int main()
{
	int n, k, d;
	while (scanf("%d%d%d", &n, &k, &d) != EOF)
	{
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;// Vertex is also a kind of number  ,dp The initial condition is very important 
		for (int i = 1; i <= n; ++i)
		{
			for (int j = 1; j <= min(i, k); ++j)
			{
				
				if (j >= d)// If the weight is greater than d, It means that all the previous schemes can add 
				{
					dp[i][1] = dp[i][1] + dp[i - j][0] + dp[i - j][1];
				}
				else
				{
					dp[i][0] = dp[i][0] + dp[i - j][0];
					dp[i][1] = dp[i][1] + dp[i - j][1];
				}
			}
			dp[i][0] %= mod;
			dp[i][1] %= mod;
		}
		printf("%lld", dp[n][1]);// Note the type of data 
	}

}

3. subject :TKKC- Light intensity

1. choice dp Up, down, left and right to maintain the maximum brightness of each square

  

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod = 1e9 + 7;
const int N = 105;
int  r[N][N];// The brightness of the point 
int  g[N][N];// The light intensity of the lamp at this point 
void solve()
{
	int a, b, m;
	scanf("%d%d%d", &a, &b, &m);
	for (int i = 1; i <= m; ++i)
	{
		int x, y, c;
		scanf("%d%d%d", &x, &y, &c);
		g[x][y] = max(g[x][y], c);
	}
	// top left corner 
	for (int i = 1; i <= a; ++i)
	{
		for (int j = 1; j <= b; ++j)
		{
			int q = g[i - 1][j]-1, p = g[i][j-1]-1;
			int t = max(q, p);
			r[i][j] = max(max(r[i][j], t), g[i][j]);
		}
	}
	// The lower right corner 
	for (int i = a; i >=1 ; i--)
	{
		for (int j = b; j >= 1; j--)
		{
			int q = g[i+1 ][j]-1, p = g[i][j+1]-1;
			int t = max(q, p);
			r[i][j] = max(max(r[i][j], t), g[i][j]);
		}
	}
	// Upper right corner 
	for (int i = 1; i <= a; ++i)
	{
		for (int j = b; j >= 1; --j)
		{
			int q = g[i - 1][j]-1, p = g[i][j+1]-1;
			int t = max(q, p);
			r[i][j] = max(max(r[i][j], t), g[i][j]);
		}
	}
	for (int i = 1; i <= a; ++i)
	{
		for (int j = 1; j <= b; ++j)
		{
			int q = g[i + 1][j]-1, p = g[i][j-1]-1;
			int t = max(q, p);
			r[i][j] = max(max(r[i][j], t), g[i][j]);
		}
	}
	for (int i = 1; i <= a; ++i)
	{
		for (int j = 1; j <= b; ++j)
		{
			if (j != 1)
			{
				printf(" ");
			}
			printf("%d", r[i][j]);
		}
	}
	printf("\n");
}
int main()
{
	solve();
	return 0;
}