Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

今天的作业题(状压dp)

Posted by jesseliu612 at 2016-07-29 11:28:58 on Problem 1185
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator