首页 > 代码库 > HDU 4539郑厂长系列故事――排兵布阵(状压DP)
HDU 4539郑厂长系列故事――排兵布阵(状压DP)
HDU 4539 郑厂长系列故事――排兵布阵
基础的状压DP,首先记录先每一行可取的所哟状态(一行里互不冲突的大概160个状态),
直接套了一个4重循环居然没超时我就呵呵了
1 //#pragma comment(linker,"/STACK:102400000,102400000") 2 #include <map> 3 #include <set> 4 #include <stack> 5 #include <queue> 6 #include <cmath> 7 #include <ctime> 8 #include <vector> 9 #include <cstdio> 10 #include <cctype> 11 #include <cstring> 12 #include <cstdlib> 13 #include <iostream> 14 #include <algorithm> 15 using namespace std; 16 #define INF 1e8 17 #define inf (-((LL)1<<40)) 18 #define lson k<<1, L, mid 19 #define rson k<<1|1, mid+1, R 20 #define mem0(a) memset(a,0,sizeof(a)) 21 #define mem1(a) memset(a,-1,sizeof(a)) 22 #define mem(a, b) memset(a, b, sizeof(a)) 23 #define FOPENIN(IN) freopen(IN, "r", stdin) 24 #define FOPENOUT(OUT) freopen(OUT, "w", stdout) 25 template<class T> T CMP_MIN(T a, T b) { return a < b; } 26 template<class T> T CMP_MAX(T a, T b) { return a > b; } 27 template<class T> T MAX(T a, T b) { return a > b ? a : b; } 28 template<class T> T MIN(T a, T b) { return a < b ? a : b; } 29 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; } 30 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b; } 31 32 //typedef __int64 LL; 33 //typedef long long LL; 34 const int MAXN = 10000; 35 const int MAXM = 100005; 36 const double eps = 1e-13; 37 //const LL MOD = 1000000007; 38 39 int N, M; 40 int ma[110]; 41 int dp[2][200][200]; 42 43 int stNum; 44 int st[1000], num[1000]; 45 46 int judge(int x) 47 { 48 if(x & (x<<2)) return 0; 49 return 1; 50 } 51 52 int get1(int x) 53 { 54 int ret = 0; 55 while(x) 56 { 57 ret += x & 1; 58 x >>= 1; 59 } 60 return ret; 61 } 62 63 void init() 64 { 65 mem1(dp);mem0(ma); 66 stNum = 0; 67 for(int i=0;i<(1<<M);i++) if(judge(i)) 68 { 69 st[stNum] = i; 70 num[stNum++] = get1(i); 71 } 72 } 73 74 75 int main() 76 { 77 //FOPENIN("in.txt"); 78 while(~scanf("%d %d%*c", &N, &M)) 79 { 80 init(); 81 int x, cur = 0; 82 for(int i=1;i<=N;i++) 83 for(int j=0;j<M;j++) { 84 scanf("%d", &x); 85 if(x==0) ma[i] |= (1<<j); 86 } 87 for(int i=0;i<stNum;i++) { 88 if(st[i] & ma[1]) continue; 89 dp[cur][i][0] = num[i]; 90 } 91 for(int r = 2; r <= N; r ++) 92 { 93 cur = !cur; 94 for(int i = 0; i < stNum; i ++) 95 { 96 if(st[i] & ma[r]) continue; 97 for(int j = 0; j < stNum; j ++ ) 98 { 99 if(st[j] & ma[r-1]) continue;100 int p = (st[i]<<1) | (st[i]>>1);101 if(st[j] & p) continue;102 for(int k = 0; k < stNum; k ++) if(dp[!cur][j][k] != -1)103 {104 int pp = st[i] | ((st[j]<<1) | (st[j]>>1));105 if(st[k] & pp) continue;106 dp[cur][i][j] = MAX(dp[cur][i][j], dp[!cur][j][k] + num[i]);107 }108 109 }110 }111 }112 int ans = 0;113 for(int i=0;i<stNum;i++) for(int j=0;j<stNum;j++)114 ans = MAX(ans, dp[cur][i][j]);115 printf("%d\n", ans);116 }117 return 0;118 }119 120 121 /*122 123 6124 3125 2126 12127 128 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。