首页 > 代码库 > ural False Mirrors(dfs)
ural False Mirrors(dfs)
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; }
ural False Mirrors(dfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。