dfs
小白不会动态规划,就暴力拿点分吧~
在acwing和蓝桥杯都试过了,能过3个数据
思路: 这道题类似于全排列问题,题目要什么样的数,那就去构造这种数就好了
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Scanner;
public class Main {
static StreamTokenizer sts = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int next() throws IOException {
sts.nextToken();
return (int) sts.nval;
}
static int N = 2 * 100000 + 10;
// 存放第几层填写了那个数
static int[] path = new int[N];
static int n, m;
static int MOD = 998244353;
static int res;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
dfs(1, 0);
System.out.println(res);
}
/**
* @param u 当前是第几层,第几个位置 u从1开始
* @param sum 前5个连续数位的和
*/
static void dfs(int u, int sum) {
/*
* 奇数数位上是奇数,偶数数位上是偶数。
* 且 5 个连续数位的和都不大于 m
*/
// 如果当前层数>5层
if (u > 5) {
// 先判断前5层的数字之和是否大于m
if (sum > m) {
return;
}
// 比如当前是在第6层,也就是当前层要填的是第6个位置的数,
// 因为我们要求的是连续5个数字的和
// 所以把第1个数字丢掉(减去第1个数字),这里我用的是滑动窗口的思想
// 后面的sum + i(i是当前层数字),就又是连续5个数字的和了
sum -= path[u - 5];
}
// 每个空都填完了之后,这个数就是符合条件的
// 因为我们在奇数位填了奇数,偶数位填了偶数,也判断了连续5个数字的和<=m
if (u == n + 1) {
res = (res + 1) % MOD;
return;
}
// 奇数位
if ((u & 1) == 1) {
for (int i = 0; i < 9; i++) {
if ((i & 1) == 1) {
// 填奇数
path[u] = i;
dfs(u + 1, sum + i);
// 这里不需要回复现场 path[i]=0
}
}
} else {
// 偶数位
for (int i = 0; i < 9; i++) {
if ((i & 1) == 0) {
// 填偶数
path[u] = i;
dfs(u + 1, sum + i);
}
}
}
}
}