xtu oj 1331 密码

矜(bai)持(gei)的云拏

已于 2023-10-15 21:33:09 修改

阅读量1.3k

点赞数 4

分类专栏： XTU OJ 文章标签：算法 c++ 动态规划

于 2022-10-27 22:13:17 首次发布

本文链接：https://blog.csdn.net/m0_73687800/article/details/127561890

版权

XTU OJ 专栏收录该内容

11 篇文章 2 订阅

订阅专栏

题目还是不复制了，自己去看

此题为动态规划。

我的AC代码思路还是一眼就可以看出来的，不废话，直接上代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll ans[46] = {0}, dp[46][5] = {0};
int main() {
	int t;
	cin >> t;
	ans[1] = 4;
	dp[1][1] = 1;
	dp[1][2] = 1;
	dp[1][3] = 1;
	dp[1][4] = 1;
	int i;
	for (i = 2; i < 46; i++) {
		dp[i][1] = dp[i - 1][2] + dp[i - 1][3];
		dp[i][2] = dp[i - 1][1] + dp[i - 1][3] + dp[i - 1][4];
		dp[i][3] = dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][4];
		dp[i][4] = dp[i - 1][2] + dp[i - 1][3];
		ans[i] += dp[i][1] + dp[i][2] + dp[i][3] + dp[i][4];
	}
	while (t--) {
		int n;
		cin >> n;
		cout << ans[n] << endl;
	}
	return 0;
}

解释一下，n=1时，只有1，2，3，4这四种情况，即1+1+1+1。

n=2时，我们假设第一位上仍为1，2，3，4，此时看第二位的情况：

1->2,3

2->1,3,4

3->1,2,4

4->2,3

不难看出情况种类为2+3+3+2，且n位为1，4时对应n+1位为两种可能，n位为2，3时对应n+1位为三种情况.

依此类推，n=3时我们只需确定第三位情况（一二位情况在n=1，2时已得出），可能性分别为

（3+3）+（2+3+2）+（2+3+2）+（3+3）=26种。

由上述可得，此题为动规，且递归方程如下：

        dp[i][1] = dp[i - 1][2] + dp[i - 1][3];
		dp[i][2] = dp[i - 1][1] + dp[i - 1][3] + dp[i - 1][4];
		dp[i][3] = dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][4];
		dp[i][4] = dp[i - 1][2] + dp[i - 1][3];

动动小手点歌赞趴，关注也是可以的哦~~