CodeChef Max-digit Tree（动态规划）

传送门.

题解：

最主要的问题是如何判断一个数是否合法，这就需要发现性质了。

这个状态划分还是不太容易想到，

每次加的数\(∈[0,k)\)，也就是个位一直在变变变，更高的位每次都是加一，这启发我们状态的划分。

这个时候可以利用数位dp的逐位确定思想，在尝试后，发现可以从高位到低位，因为当高位确定后，高位就不会变了，那么高位的最大值也就确定了。

设\(f[i][p][a]\)，\(i\)含义如上，\(i+1\)位后的最大值是p，\(2-i\)位是0，当前个位是\(a\)，使第\(i\)位加1后个位变成什么？

\(i=2\)时直接暴力处理，\(f[i]\)可以\(O(k)\)由\(f[i-1]\)推出来，复杂度\(O(n*k^3)\)。

有了f方便处理出\(g[i][p][x][a]\)，\(i、p、a\)含义如上，x表示第i位要+x，

这里\(x=0\)，g的值就是a，然后g自己推自己，复杂度\(O(n*k^3)\)。

接下来的部分就很傻逼了，带根联通块，直接在dfs序上dp，做到个位的时候，再跳跳看能不能跳到那个位去就好了。

Code：

#include<bits/stdc++.h>

#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)

#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)

#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)

#define ll long long

#define pp printf

#define hh pp("\n")

using namespace std;

const int N = 505;

int n, k;

int d[N], x, y;

vector<int> e[N];

#define pb push_back

#define si size()

int p[N], q[N], np[N], p0, fa[N];

void dg(int x) {

	p[x] = ++ p0; np[p0] = x;

	ff(j, 0, e[x].si) {

		int y = e[x][j];

		if(fa[x] != y) fa[y] = x, dg(y);

	}

	q[x] = p0;

}

const int mo = 1e9 + 7;

int f[N][10][10], g[N][10][10][10];

ll h[N][N][10][10];

void add(ll &x, ll y) {

	(x += y) >= mo ? x -= mo : 0;

}

int T;

int main() {

//	freopen("buried.in", "r", stdin);

//	freopen("buried.out", "w", stdout);

	k = 10;

	for(scanf("%d", &T); T; T --) {

		fo(i, 1, n) e[i].clear();

		memset(h, 0, sizeof h);

		fo(i, 1, n) fa[i] = 0; p0 = 0;

		scanf("%d", &n);

		fo(i, 1, n - 1) {

			scanf("%d %d", &x, &y);

			e[x].pb(y); e[y].pb(x);

		}

		fo(i, 1, n) scanf("%d", &d[i]);

		fo(i, 1, n) sort(e[i].begin(), e[i].end());

		dg(1);

		//Initialization of F

		ff(p, 0, k) {

			ff(a, 0, k) if(p || a) {

				int x = a;

				while(x < k) {

					x += max(x, p);

				}

				f[1][p][a] = x % k;

			}

		}

		//dp F

		fo(i, 2, n - 1) {

			ff(p, 0, k) {

				ff(a, 0, k) {

					int x = a;

					fo(c, 1, k) x = f[i - 1][max(p, c - 1)][x];

					f[i][p][a] = x;

				}

			}

		}

		//dp g

		fo(i, 2, n) {

			ff(p, 0, k) {

				ff(a, 0, k) {

					g[i][p][0][a] = a;

					ff(x, 1, k) g[i][p][x][a] = f[i - 1][max(x - 1, p)][g[i][p][x - 1][a]];

				}

			}

		}

		//dp h

		ll ans = 0;

		fo(j, 1, n) h[1][j][0][1] = 1;

		fo(i, 1, n) {

			int num = d[np[i]];

			int ni = q[np[i]] + 1;

			fo(j, 2, n) {

				ff(p, 0, k) ff(a, 0, k) if(h[i][j][p][a] && (p || a)) {

					add(h[i + 1][j - 1][max(p, num)][g[j][p][num][a]], h[i][j][p][a]);

					add(h[ni][j][p][a], h[i][j][p][a]);

				}

			}

			ff(p, 0, k) ff(a, 0, k) if(h[i][1][p][a] && (p || a)) {

				int x = a;

				while(x < num) x += max(x, p);

				if(x == num) add(ans, h[i][1][p][a]);

				add(h[ni][1][p][a], h[i][1][p][a]);

			}

		}

		pp("%lld\n", ans);

	}

}

巴特西

CodeChef Max-digit Tree（动态规划）

题解：

Code：

最新文章

热门文章