dp问题集

”Strive for greatness"

                                                                                      --2021.8.29

1.状压dp:

有一个N*M(N<=5,M<=1000)的棋盘，现在有1*2及2*1的小木块无数个，要盖满整个棋盘，有多少种方式？答案只需要mod1,000,000,007即可。

考虑用二进制存储每一行的状态 比如00100表示第3行放着一个盒子,状压的核心思想

state代表当前行的状态 nex代表其对下一列产生的影响(例如横着放木块)

AC代码:

#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]表示前i-1列的方案数
int n, m;
//枚举到第i列 ,第j行 以及第j行的状态 以及其对下一列产生的影响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)//假如已经该行迎接被上一列给占了 就跳过
	{
		dfs(i, j + 1, state, nex);
	}
	if ((state) & (1 << j) == 0)//如果该行为空 就放1个2*1的方格 
	{
		dfs(i, j + 1, state, nex | (1 << j));//把nex的第j位变为1,横着放会对下一列产生影响
	}
	if ((j + 1) < n && ((state) & (1 << (j + 1))) == 0 && ((state) & (1 << j) == 0))
	{
		dfs(i, j + 2, state, nex);//则跳过两行
	}
	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])//如果存在方案数，则推广到下一列
				{
					dfs(i, 0, j, 0);
				}
			}
		}
		printf("lld\n", dp[m + 1][0]);
	}
}

2.题目:Problem - 431C - Codeforces

  题目大意：一种特殊的树,每个顶点有k个边,其中权值分别为1~k,问能找到多少条即满足权值之和为n且其中至少一条边的权值之和大于d的路径条数

  题解:1.dp[i][0]代表权值之和为i且不满足条件,dp[i][1]则满足条件

          2.此时若对于当前边的权值j>=d,则将原先dp[i-j][0]+dp[i-j][1]方案全部加过来

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

             否则

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

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

         AC代码:

#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;//顶点也算一种条数 ,dp题初始条件很重要
		for (int i = 1; i <= n; ++i)
		{
			for (int j = 1; j <= min(i, k); ++j)
			{
				
				if (j >= d)//若此时权重大于d,则代表之前的方案全都能加
				{
					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]);//注意数据类型
	}

}

3.题目:TKKC-光照强度

1.选择dp上下左右去维护每个方块的亮度的最大值

  

#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];//该点的亮度
int  g[N][N];//该点的灯的光照强度
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);
	}
	//左上角
	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 = 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]);
		}
	}
	//右上角
	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;
}