本文主要是介绍九小时九个人九扇门题解报告,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
九小时九个人九扇门题解报告
标签:动态规划,数字根
题目链接
来源:牛客网
解题思路:
树字根
首先是对于数字根的求解,我们可以自行设置函数模拟算出,也可以采用更快的公式法。
数字根具有这样的性质:x+9与x的数根相同,即一个数加9后它的数根不变。因此数a的树根就是a对9取模后的结果。
求数根公式:a的数根b = (a-1) % 9+1
树根性质的证明:
(abcd)% 9 = (a * 1000+b * 100+c * 10+d) % 9
= a%9+b%9+c%9+d%9
=(a+b+c+d)%9
动态规划(背包)
首先思考状态如何转移,设置如下数组dp[i-1][j],表示前i人中能够打开第j扇门的最大组合数,此时我们考虑再添一人,这个人就叫我好了,加入我之后各个门的最大组合数会如何改变,我们可以把最大组合数分成三部分考虑:
有我没其他人: dp[i][a[i]]=1;
有其他人没我:dp[i][j]=(dp[i][j]+dp[i-1][j])%M;
有我有其他人:dp[i][(j+a[i]-1)%9+1]=(dp[i][(j+a[i]-1)%9+1]+dp[i-1][j])%M
代码实现:
#include <iostream>
#include <stdio.h>
using namespace std;
int a[100500];
int dp[100500][10];
const int M=998244353;
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];a[i]=(a[i]-1)%9+1;}for(int i=1;i<=n;i++){dp[i][a[i]]=1;for(int j=1;j<=9;j++){dp[i][j]=(dp[i][j]+dp[i-1][j])%M;dp[i][(j+a[i]-1)%9+1]=(dp[i][(j+a[i]-1)%9+1]+dp[i-1][j])%M;}}for(int i=1;i<=9;i++){cout<<dp[n][i]<<" ";}return 0;
}
这篇关于九小时九个人九扇门题解报告的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!