题意：有N个国家，每个国家属于一个洲，现在有人要来攻击一些国家，每次攻击选择来自三个不同洲的国家，我们能够选择去保护一个国家，被保护的国家恐惧值-2，其余两个国家恐惧值+2，和这两个国家在一个洲的国家恐惧值+1。
分析：由于超过5点恐惧值就以及超过极限了，而每次攻击又会带来其余两个洲恐惧值的增加，因此最多在不超过10天的情况下将会出现有国家超过5点恐惧值。
代码如下：
#include#include #include #include #include using namespace std;int N, M, K;char val[20], con[20];char kill[105][5];bool fail() { for (int i = 0; i < N; ++i) { if (val[i] > 5) return true; } return false;}inline void fix(char &x) { if (x < 1) x = 1;}void modify(int x, int p) { // x天，支援第kill[x][i]个国家 char a = kill[x][p], b = kill[x][(p+1)%3], c = kill[x][(p+2)%3]; val[a] -= 2, fix(val[a]); val[b] += 2, val[c] += 2; for (int i = 0; i < N; ++i) { if (con[i] == con[a]) continue; if (i == b || i == c) continue; if (con[i] == con[b]) val[i] += 1; if (con[i] == con[c]) val[i] += 1; }}bool dfs(int x, int end) { // return 1 表示存在一种方案使得所有国家安然无恙// printf("x = %d\n", x); if (fail()) { // 中间任何一天有国家超过了5点恐慌说明该种方案失败 return false; } if (x == end+1) { // 熬到了第end+1天，说明有一种方案平安度过了前面end天 return true; } char cpy[20]; memcpy(cpy, val, sizeof (val)); for (int i = 0; i < 3; ++i) { // 第x天，支援第kill[x][i]个国家 modify(x, i); if (dfs(x+1, end)) { return true; } memcpy(val, cpy, sizeof (cpy)); } return false;}int main() { int T; scanf("%d", &T); for (int ca = 1; ca <= T; ++ca) { scanf("%d %d %d", &N, &M, &K); for (int i = 0; i < N; ++i) { scanf("%d", &con[i]); // 说明该国家属于哪一个洲 } for (int i = 0; i < N; ++i) { scanf("%d", &val[i]); } for (int i = 0; i < K; ++i) { for (int j = 0; j < 3; ++j) { scanf("%d", &kill[i][j]); } } int ans = K; char cpy[20]; // 由于有一个最小不低于1的限制，因此不能在原来基础上进行恢复 for (int i = 0; i < K; ++i) { memcpy(cpy, val, sizeof (val)); // 这里没有记录原来的值，导致错了很久 if (!dfs(0, i)) { ans = i; break; } memcpy(val, cpy, sizeof (cpy)); } printf("Case #%d: %d\n", ca, ans); } return 0;}
BFS版本：
#include#include #include #include #include using namespace std;int N, M, K, ans;char val[20], con[20];char kill[105][5];bool fail(char val[]) { for (int i = 0; i < N; ++i) { if (val[i] > 5) return true; } return false;}inline void fix(char &x) { if (x < 1) x = 1;}void modify(char val[], int x, int p) { // x天，支援第kill[x][i]个国家 int a = kill[x][p], b = kill[x][(p+1)%3], c = kill[x][(p+2)%3]; val[a] -= 2, fix(val[a]); val[b] += 2, val[c] += 2; for (int i = 0; i < N; ++i) { if (con[i] == con[a]) continue; if (i == b || i == c) continue; if (con[i] == con[b]) val[i] += 1; if (con[i] == con[c]) val[i] += 1; }}struct Que { char val[20]; char day;}q[1000000], pos;int front, tail;void bfs() { front = tail = 0; q[tail].day = 0; memcpy(q[tail++].val, val, sizeof (val)); while (front != tail) { pos = q[front++]; ans = pos.day; if (pos.day >= K) continue; for (int i = 0; i < 3; ++i) { q[tail] = pos; modify(q[tail].val, pos.day, i); if (!fail(q[tail].val)) { q[tail++].day = pos.day + 1; } } }}int main() { int T; scanf("%d", &T); for (int ca = 1; ca <= T; ++ca) { scanf("%d %d %d", &N, &M, &K); for (int i = 0; i < N; ++i) { scanf("%d", &con[i]); // 说明该国家属于哪一个洲 } for (int i = 0; i < N; ++i) { scanf("%d", &val[i]); } for (int i = 0; i < K; ++i) { for (int j = 0; j < 3; ++j) { scanf("%d", &kill[i][j]); } } bfs(); printf("Case #%d: %d\n", ca, ans); } return 0;}