九小时九个人九扇门

 

https://ac.nowcoder.com/acm/contest/23106/A

对于每个人来说,他们都有一个数,并且这些数的范围是 [0 , 9] 我们很容易的想到使用DP的思路来解决问题。

我们设 f[n , m] 表示前 n 个人一共可以组合出来多少个结果为 m 的个数。 那么我们便可以得到这样的转移式子对于第 i 个人来说,其本身就是一种情况,因此 f[i , v[i]] ++ 是必要的。那么对于前一个位的 10 种情况而言假设原根为 g(x) ,那么状态转移方程如下所示

\[f(i,j) = \sum_{g(v[i]+k)=j} f(i-1,k)\]

转化为代码

1
2
3
4
5
6
for (int i = 1 ; i <= n ; i ++) {
  f[i][v[i]] = 1;
  for (int j = 0 ; j <= 9 ; j ++) {
    f[i][g(v[i] + j)] += f[i - 1][j];
  }
}

code

algorithm