本文主要是介绍ural False Mirrors (状态压缩+记忆化搜索)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.timus.ru/problem.aspx?space=1&num=1152
有n个阳台围城一圈，每个阳台都有若干个怪兽，一次可以打三个相邻的阳台上的怪兽，它们就会全部死去，但攻击者会受到没有死去怪兽的攻击，每个怪兽的攻击是1unit，问最后攻击者受到的最小伤害。
n <= 20，可以直接dfs过去。
1次WA，1次TLE。
WA是没看透题意，我判断的递归终止的条件是怪兽数目小于等于3，这是不对的，就算怪兽数目小于等于3，也不一定能一次打完，因为它只能打连续的怪兽，若两个怪兽之间的距离大于等于2，那么还需要一次才能打完。
TLE因为没加剪枝，dfs的过程中一旦发现已受攻击值大于最优值，就返回。
#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL __int64
#define eps 1e-12
#define PI acos(-1.0)
#define PP pair<LL,LL>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1000;
const int mod = 1000000009;int a[22],vis[22];
int Min;
int n;
void dfs(int num,int sum,int att)
{if(att >= Min) //TLE的关键！return;if(num == 1){Min = min(Min,att);return;}//判断没死的怪兽的位置是否相邻，只有相邻递归才结束else if(num == 2){int p[3],cnt=0;for(int i = 1; i <= n; i++)if(!vis[i])p[++cnt] = i;if(p[2] - p[1] <= 1 || p[2]-p[1] == n-1){Min = min(Min,att);return;}}else if(num == 3){int p[3],cnt = 0;for(int i = 1; i <= n; i++){if(!vis[i]){if(i <= n-2 && !vis[i+1] && !vis[i+2]){Min = min(Min,att);return;}else if(!vis[n-1] && !vis[n] && !vis[1]){Min = min(Min,att);return;}}}}for(int i = 1; i <= n; i++){if(!vis[i]){int tmp = 0,f1 = 0,f2 = 0,t;vis[i] = 1;tmp += a[i];if(i > 1 && !vis[i-1]){vis[i-1] = 1;tmp += a[i-1];f1 = 1;}else if(i == 1 && !vis[n]){vis[n] = 1;tmp += a[n];f1 = 1;}if(i < n && !vis[i+1]){vis[i+1] = 1;tmp += a[i+1];f2 = 1;}else if(i == n && !vis[1]){vis[1] = 1;tmp += a[1];f2 = 1;}t = sum - tmp;dfs(num-1-f1-f2,t,att+t);vis[i] = 0;if(i > 1 && f1 == 1)vis[i-1] = 0;else if(i == 1 && f1 == 1)vis[n] = 0;if(i < n && f2 == 1)vis[i+1] = 0;else if(i == n && f2 == 1)vis[1] = 0;}}
}int main()
{int sum;while(~scanf("%d",&n)){sum = 0;for(int i = 1; i <= n; i++){scanf("%d",&a[i]);sum += a[i];}Min = INF;memset(vis,0,sizeof(vis));dfs(n,sum,0);printf("%d\n",Min);}return 0;
}
又换了一种新姿势，因为n<=20，且每个怪物在一种状态下只有0和1两个选择，所以共有(1<<n)-1种状态，然后记忆化搜索。
#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL __int64
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 50010;int n,num[22];
int dp[(1<<20)+10];int dfs(int sta)
{if(dp[sta] != INF)return dp[sta];int ss,a,b;for(int i = 1; i <= n; i++){if(sta&(1<<(i-1))){ss = sta;a = (i == 1?n:i-1);b = (i == n?1:i+1);ss -= (1<<(i-1));if(ss&(1<<(a-1)))ss -= (1<<(a-1));if(ss&(1<<(b-1)))ss -= (1<<(b-1));int tmp = 0;for(int j = 1; j <= n; j++)if(ss & (1<<(j-1)) )tmp += num[j];dp[sta] = min(dp[sta],dfs(ss)+tmp);}}return dp[sta];
}int main()
{while(~scanf("%d",&n)){for(int i = 1; i <= n; i++)scanf("%d",&num[i]);memset(dp,INF,sizeof(dp));dp[0] = 0;printf("%d\n",dfs((1<<n)-1));}return 0;
}
这篇关于ural False Mirrors (状态压缩+记忆化搜索)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
