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