建一个网站需要什么/seo排名赚

https://vjudge.net/problem/HDU-4539

一道不太容易的状压DP

之前必须要处理一下

单纯的DP二进制会爆好久没押行写了

(请不要理会一个押行选手

Code of AC:

#include<bits/stdc++.h>
using namespace std;
bool check(int x,int y){return ((x<<1)&y)==0&&(((x>>1)&y)==0);}
int count(int x){int ans=0;while(x){if(x&1>0)++ans;x>>=1;}return ans;
}
int DP[110][220][220],A[110],C[220],S[220];
int main(){int n,m,x,tot;while(cin>>n>>m){tot=0;memset(A,0,sizeof A);memset(DP,0,sizeof DP);memset(C,0,sizeof C);memset(S,0,sizeof S);for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){cin>>x;if(x) A[i]|=(1<<(j-1));}m=(1<<m)-1;for(int i=0;i<=m;++i){if(((i&(i<<2))>0)||((i&(i>>2))>0)) continue;S[++tot]=i;C[tot]=count(i);}for(int i=1;i<=n;++i){for(int j=1;j<=tot;++j){if((A[i]|S[j])!=A[i]) continue;for(int k=1;k<=tot;++k){if(check(S[j],S[k])==0) continue;for(int l=1;l<=tot;++l){if((S[j]&S[l])>0) continue;DP[i][j][k]=max(DP[i][j][k],DP[i-1][k][l]+C[j]);}}}}int ans=0;for(int i=1;i<=tot;++i)for(int j=1;j<=tot;++j)ans=max(ans,DP[n][i][j]);cout<<ans<<endl;}
}