英雄每秒钟可以摧毁三个连续的阳台(大Google给出的翻译。。 。 ),剩余阳台上的怪物每秒钟会对英雄造成一个单位的伤害。为英雄受到伤害的最小值是多少。
阳台数 n <= 20,且每个阳台只有两种状态。显然是状态压缩( 昨天尚神刚刚讲的→,→ )。
算了一下最多会用九秒钟,然后计算次数大约是这样(1<<20)*9,时限2000MS,所以尽情的暴力吧。
话说写代码的时候我正在看自己的位运算的博客. . . . . .然后南壕不屑的看了我一眼走了. . . . . .我没翻题解啊
状态转移方程 dp[ t ][ sta ] = min( dp[ t+1 ][ next_sta ] + next_sta中存在的怪兽和).
#include <iostream> #include <algorithm> #include <cstdlib> #include <cstdio> #include <cstring> #include <queue> #include <cmath> #include <stack> #pragma comment(linker, "/STACK:1024000000"); #define LL long long int #define ULL unsigned long long int #define _LL __int64 #define INF 0x3f3f3f3f #define Mod 1000000009 using namespace std; int num[25]; int Min; int dp[10][(1<<20)+10]; int dfs(int t,int sta,int n) { // cout<<"t = "<<t<<" sta = "<<sta<<endl; if(t > 9) return (1<<20); if(dp[t][sta] != -1) return dp[t][sta]; int i,temp,dag,j; for(i = 0;i < n; ++i) { temp = sta; if((temp&(1<<i))) { temp = (temp&(~(1<<i))); //左2 if(i == 0) { temp = (temp&(~(1<<(n-1)))); temp = (temp&(~(1<<(n-2)))); dag = dfs(t+1,temp,n); } else if(i == 1) { temp = (temp&(~(1))); temp = (temp&(~(1<<(n-1)))); dag = dfs(t+1,temp,n); } else { temp = (temp&(~(1<<(i-1)))); temp = (temp&(~(1<<(i-2)))); dag = dfs(t+1,temp,n); } for(j = 0;j < n; ++j) { if((temp&(1<<j))) dag += num[j]; } if(dp[t][sta] == -1 || dp[t][sta] > dag) { dp[t][sta] = dag; } temp = sta,dag = 0; // 右2 if(i == n-1) { temp = (temp&(~(1<<(0)))); temp = (temp&(~(1<<(1)))); dag = dfs(t+1,temp,n); } else if(i == n-2) { temp = (temp&(~(1))); temp = (temp&(~(1<<(n-1)))); dag = dfs(t+1,temp,n); } else { temp = (temp&(~(1<<(i+1)))); temp = (temp&(~(1<<(i+2)))); dag = dfs(t+1,temp,n); } for(j = 0;j < n; ++j) { if((temp&(1<<j))) dag += num[j]; } if(dp[t][sta] == -1 || dp[t][sta] > dag) { dp[t][sta] = dag; } temp = sta,dag = 0; //左右各一 if(i == 0) { temp = (temp&(~(1<<(n-1)))); temp = (temp&(~(1<<(1)))); dag = dfs(t+1,temp,n); } else if(i == n-1) { temp = (temp&(~(1))); temp = (temp&(~(1<<(n-2)))); dag = dfs(t+1,temp,n); } else { temp = (temp&(~(1<<(i-1)))); temp = (temp&(~(1<<(i-2)))); dag = dfs(t+1,temp,n); } for(j = 0;j < n; ++j) { if((temp&(1<<j))) dag += num[j]; } if(dp[t][sta] == -1 || dp[t][sta] > dag) { dp[t][sta] = dag; } } } return dp[t][sta]; } int main() { //freopen("sadfsdaf.txt","w",stdout); int n,i,sum = 0; scanf("%d",&n); for(i = 0;i < n; ++i) { scanf("%d",&num[i]); sum += num[i]; } Min = INF; int sta = (1<<n)-1; for(i = 0;i < 10; ++i) { memset(dp[i],-1,sizeof(int)*(sta+3)); } for(i = 0;i <= 10; ++i) { dp[i][0] = 0; } dfs(0,sta,n); int Min = (1<<20); for(i = 0;i < 10; ++i) { if(dp[i][sta] != -1 && dp[i][sta] < Min) Min = dp[i][sta]; } printf("%d\n",Min); return 0; }
URAL 1152 False Mirrors 状压+记忆化搜索,布布扣,bubuko.com
URAL 1152 False Mirrors 状压+记忆化搜索
原文:http://blog.csdn.net/zmx354/article/details/19931735