九小时九个人九扇门题解报告

九小时九个人九扇门题解报告

九小时九个人九扇门题解报告

标签：动态规划，数字根

题目链接

来源：牛客网

解题思路：

树字根

首先是对于数字根的求解，我们可以自行设置函数模拟算出，也可以采用更快的公式法。
数字根具有这样的性质：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；
}