| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
今天的作业题(状压dp)#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int zt[63]={-1,0,1,2,4,8,9,16,17,18,32,33,34,36,64,65,66,68,72,73,128,129,130,132,136,137,144,145,146,256,257,258,260,264,265,272,273,274,288,289,290,292,512,513,514,516,520,521,528,529,530,544,545,546,548,576,577,578,580,584,585,99999};
int ky[11]={0,1,3,7,15,31,63,127,255,511,585};
int img[100+10];
int f[100+10][61+10][61+10];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char ch=getchar();
while(ch!='P' && ch!='H')ch=getchar();
img[i]*=2;
if(ch=='H')img[i]+=1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;zt[j]<=ky[m];j++){
for(int k=1;zt[k]<=ky[m];k++){
int& fnow=f[i][j][k];
fnow=0;
int t;
for(int p=1;zt[p]<=ky[m];p++){
if( ((zt[j] & zt[k])==0) && ((zt[k] & zt[p])==0) && ((zt[j] & zt[p])==0) && ( (zt[j] & img[i]) == 0 ) && ( (zt[k] & img[i-1]) == 0 ) && ( (zt[p] & img[i-2]) == 0 )){
t=f[i-1][k][p]+__builtin_popcount(zt[j]);
fnow=max(fnow,t);
}
}
}
}
}
int ans=0;
for(int j=0;zt[j]<=ky[m];j++){
for(int k=0;zt[k]<=ky[m];k++){
ans=max(ans,f[n][j][k]);
}
}
printf("%d",ans);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator