首页 > 代码库 > URAL 1152. False Mirrors （记忆化搜索 状压DP）
URAL 1152. False Mirrors （记忆化搜索 状压DP）
题目链接
题意 ： 每一颗子弹破坏了三个邻近的阳台。（第N个阳台是与第1个相邻）射击后后的生存的怪物都对主角造成伤害- 如此，直到所有的怪物被消灭，求怎样射击才能受到最少伤害。
思路 ： 状压，数据不是很大，可以爆一爆，或者DFS下去就行，枚举每一种状态。
1 //1152 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define oo 1 << 28 6 using namespace std ; 7 8 int a[110],dp[1 << 21] ; 9 bool vis[1 << 21] ;10 int n ;11 12 int DFS(int sta,int sum)13 {14 if(vis[sta]) return dp[sta] ;15 vis[sta] = true ;16 if(sta == 0) return dp[sta] = 0 ;17 int ans = oo ;18 for(int i = 0 ; i < n ; i++)19 {20 int newsta = sta ,newsum = sum ;21 for(int j = i-1 ; j <= i+1 ; j++)22 {23 int k = j ;24 if(j == -1) k = n-1 ;25 else if(j == n) k = 0 ;26 if(newsta & (1 << k))27 {28 newsta -= (1 << k) ;29 newsum -= a[k] ;30 }31 }32 if(newsta != sta)33 ans = min(ans,DFS(newsta,newsum)+newsum) ;34 }35 return dp[sta] = ans ;36 }37 int main()38 {39 while(~scanf("%d",&n))40 {41 int sum = 0 ;42 memset(a,0,sizeof(a)) ;43 memset(dp,63,sizeof(dp)) ;44 memset(vis,false,sizeof(vis)) ;45 for(int i = 0 ; i < n ; i++)46 {47 scanf("%d",&a[i]) ;48 sum += a[i] ;49 }50 dp[(1 << n)-1] = 0 ;51 printf("%d\n",DFS((1 << n)-1,sum)) ;52 }53 return 0 ;54 }
URAL 1152. False Mirrors （记忆化搜索 状压DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。