Pilot's Blog
0%

蓝桥oj-3362-建造房屋

发表于 更新于 分类于 ， ， Valine：
本文字数： 899 阅读时长 ≈ 1 分钟

题目

分析

确定dp含义

dp[ i ] [ j ]表示第i条街在建了j栋房子情况下的方案数量

状态转移方程

\(dp[i][j + q] = \sum_{q = i - 1}^{k}dp[i - 1][q]，其中j从1到m\)

最终状态

dp[ n ][ k ]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.Scanner;

public class Main {
	static int p = (int)1e9 + 7;
    // 为什么max要设置成下面两种形式，真的就是往大了开吗
	static int MAXN = 55;
	static int MAXK = 2605;
	static long[][] dp = new long[MAXN][MAXK];
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = scan.nextInt();
		int k = scan.nextInt();
		// 下面这个初始化不知道有什么作用
		for(int i = 0; i <= k; i++) {
			dp[0][i] = 1;
		}
		// 最外层for循环计算的是从第一条街道到第n条街道
		for(int i = 1; i <= n; i++) {
			// 中间这层for循环计算的是第i条街道上修建的房子从1到n的情况
			for(int j = 1; j <= m; j++) {
				// 最里面for循环计算的是前i - 1条街道修建的房屋数量
				// 其中最少每条街道一层房屋，有i-1条街道，所以有i-1条房屋
				// 最多就建到预算花光为止
				for(int q = i - 1; q <= k; q++) {
					dp[i][j + q] += dp[i - 1][q];
					dp[i][j + q] %= p;
				}
			}
		}
		System.out.println(dp[n][k]);
		scan.close();
	}
}

问题

MAXN, MAXK的设置

三重for循环顺序的设置

初始化dp[0]这一行