【2005-2006 ACM-ICPC, NEERC, Moscow Subregional Contest】Problem J. Jack-pot

简单dfs，差分一下A数组和建出字典树能写得更方便，若不这么做代码时就会像我一样难受。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 100003;

int a[13][N], n, m, k, A[13], pos[13][N];

ll dfs(int tmp, int l, int r, int f) {

	if (tmp > m) {

		return 1ll * (r - l + 1) * A[m];

	}

	int und = l;

	ll ans = 1000000000000000ll;

	if (r - l + 1 < k || (a[tmp][l] != 0) || (a[tmp][r] != k - 1)) {

		ans = 1ll * A[tmp - 1] * (r - l + 1);

		if (a[tmp][l] != 0) pos[tmp - 1][f] = 0;

		if (a[tmp][r] != k - 1) pos[tmp - 1][f] = -(k - 1);

	}

	for (int i = l + 1; i <= r; ++i)

		if (a[tmp][i] != a[tmp][i - 1] && a[tmp][i] != a[tmp][i - 1] + 1) {

			ans = 1ll * A[tmp - 1] * (r - l + 1);

			pos[tmp - 1][f] = -(a[tmp][i - 1] + 1);

			break;

		}

	for (int i = l + 1; i <= r + 1; ++i)

		if (i > r || a[tmp][i] != a[tmp][und]) {

			int num = dfs(tmp + 1, und, i - 1, und) + 1ll * A[tmp - 1] * (r - l + 1 - (i - und));

			if (num < ans) {

				ans = num;

				pos[tmp - 1][f] = und;

			}

			und = i;

		}

	return ans;

}

char s[13];

int main() {

	scanf("%d%d%d", &n, &m, &k);

	for (int i = 1; i <= m; ++i) scanf("%d", &A[i]);

	for (int i = 1; i <= n; ++i) {

		scanf("%s", s + 1);

		for (int j = 1; j <= m; ++j)

			a[j][i] = s[j] - '0';

	}

	ll ans = dfs(1, 1, n, 1); int tmp = 1;

	for (int i = 1; i <= m; ++i) {

		tmp = pos[i - 1][tmp];

		if (tmp <= 0) {

			printf("%d", -tmp);

			for (int j = i + 1; j <= m; ++j) putchar('0');

			break;

		}

		printf("%d", a[i][tmp]);

	}

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

	return 0;

}

巴特西

【2005-2006 ACM-ICPC, NEERC, Moscow Subregional Contest】Problem J. Jack-pot

最新文章

热门文章