題意：有N個國家，每個國家屬于一個洲，現在有人要來攻擊一些國家，每次攻擊選擇來自三個不同洲的國家，我們能夠選擇去保護一個國家，被保護的國家恐懼值-2，其余兩個國家恐懼值+2，和這兩個國家在一個洲的國家恐懼值+1。

分析：由于超過5點恐懼值就以及超過極限了，而每次攻擊又會帶來其余兩個洲恐懼值的增加，因此最多在不超過10天的情況下將會出現有國家超過5點恐懼值。

代碼如下：

#include <cstdlib> #include <cstring> #include <cstdio> #include <iostream> #include <algorithm> 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 <cstdlib> #include <cstring> #include <cstdio> #include <iostream> #include <algorithm> 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; }

?

轉載于:https://www.cnblogs.com/Lyush/archive/2013/03/31/2992450.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的HDU-4536 XCOM Enemy Unknown 枚举的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。