社区讨论

0分满江红求条

P1896[SCOI2005] 互不侵犯参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@m31n47ip
此快照首次捕获于
2024/11/03 21:40
去年
此快照最后确认于
2025/11/04 15:25
4 个月前
查看原帖

Code:

CPP
#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define Pii pair<int, int>
#define ULL unsigned long long

namespace gdb7
{
	LL dp[10][90][520], ok[520], cnt[520];
	int main() {
		int n, k2;
		cin >> n >> k2;
		dp[0][0][0] = 1;
		int num = 0;
		for (int i = 1; i < (1 << n); ++i) {
			int tmp = i;
			while (tmp) {
				++cnt[i];
				tmp &= (tmp - 1);
			}
			if ((((i << 1) | (i >> 1)) & i) == 0) {
				ok[++num] = i;
			}
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j < num; ++j) {
				int s1 = ok[j];
				for (int k = 1; k < num; ++k) {
					int s2 = ok[k];
					if (((s2 | (s2 << 1) | (s2 >> 1)) & s1) == 0) {
						for (int l = 0; l <= k2; ++l) {
							if (l - cnt[s1] >= 0) {
								dp[i][l][s1] += dp[i - 1][l - cnt[s1]][s2];
							}
						}
					}
				}
			}
		}
		LL ans = 0;
		for (int i = 1; i < num; ++i) {
			ans += dp[n][k2][i];
		}
		cout << ans << endl;
		return 0;
	}
};

int main()
{
	return gdb7::main();
}

全部 WA,样例输出 0。

回复

5 条回复,欢迎继续交流。

正在加载回复...