题目链接:
https://vjudge.net/contest/159644#problem/H
题意:
注意 是曼哈顿距离恰好是2，恰好！！！
题解:
与poj1185差不多的…
滚动数组，否则MLE，是我MLE了…
代码:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){ 10 ll x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 ////////////////////////////////////////////////////////////////////////// 16 const int maxn = 1e5+10; 17 18 ll dp[2][1005][1005]; 19 int num[1005],cur[105]; 20 int n,m,cnt; 21 int sta[1005]; 22 23 int getnum(int x){ 24 int res = 0; 25 while(x){ 26 if(x & 1) res++; 27 x >>= 1; 28 } 29 return res; 30 } 31 32 void init(){ 33 cnt = 0; 34 for(int i=0; i<=(1<<10); i++){ 35 if(!(i & (i<<2))){ 36 sta[cnt] = i; 37 num[cnt] = getnum(i); 38 cnt++; 39 } 40 } 41 } 42 43 int main(){ 44 init(); 45 while(cin>>n>>m){ 46 MS(cur); 47 for(int i=0; i<n; i++) 48 for(int j=0; j<m; j++){ 49 int x; cin >> x; 50 if(x == 1) cur[i] += (1<<j); 51 } 52 memset(dp,-1,sizeof(dp)); 53 int now=0,pre=1; 54 for(int i=0; i<cnt; i++){ 55 if(!(sta[i]&(~cur[0]))) 56 dp[now][i][0] = num[i]; 57 } 58 59 for(int i=1; i<n; i++){ 60 swap(now,pre); 61 for(int j=0; j<cnt; j++){ 62 if(sta[j]&(~cur[i])) continue; 63 for(int k=0; k<cnt; k++){ 64 if(sta[k]&(~cur[i-1])) continue; 65 if(((sta[j]<<1)&sta[k]) || ((sta[j]>>1)&sta[k])) continue; 66 for(int x=0; x<cnt; x++){ 67 if(i>=2 && (sta[x]&(~cur[i-2]))) continue; 68 if(sta[j]&sta[x]) continue; 69 if(dp[pre][k][x] == -1) continue; 70 dp[now][j][k] = max(dp[now][j][k],dp[pre][k][x]+num[j]); 71 } 72 } 73 } 74 } 75 76 ll ans = 0; 77 for(int i=0; i<cnt; i++) 78 for(int j=0; j<cnt; j++) 79 ans = max(ans,dp[now][i][j]); 80 81 cout << ans << endl; 82 } 83 84 return 0; 85 }