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

状态一定要从0开始枚举 状态一定要从0开始枚举 状态一定要从0开始枚举

Posted by zhuyicheng_2b at 2016-10-28 00:53:45 on Problem 1185
丑代码
#include<iostream>
#include<cstdio>
using namespace std;
int dp[101][60][60],img[101],mat[60]={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};
int getbit(int i){
	int co=0;
	while(i>0){
		if (i&1) co++;
		i>>=1;
	}
	return co;
}
inline int max(int a,int b){return a>b?a:b;}
int main(){
	//freopen("noi 2001.out","w",stdout);
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			char c;
			cin>>c; 
			img[i]<<=1;
			if (c!='P') img[i]^=1;
		} 
	for (int i=1;mat[i]<=((1<<m)-1)&&i<=59;i++)
		if ((mat[i]&img[1])==0)
		for (int j=1;mat[j]<=((1<<m)-1)&&j<=59;j++)
			 dp[1][i][j]=getbit(mat[i]);
	if (n>=2) for (int i=0;mat[i]<=((1<<m)-1)&&i<=59;i++)
				if ((mat[i]&img[2])==0)
					for (int j=0;mat[j]<=((1<<m)-1)&&j<=59;j++)
						if ((mat[i]&mat[j])==0&&(mat[j]&img[1])==0) {dp[2][i][j]=dp[1][j][1]+getbit(mat[i]);} 
	for (int i=3;i<=n;i++)
		for (int j=0;mat[j]<=((1<<m)-1)&&j<=59;j++)
			if ((img[i]&mat[j])==0)
				for (int k=0;mat[k]<=((1<<m)-1)&&k<=59;k++)
					if (((img[i-1]&mat[k])==0)&&((mat[k]&mat[j])==0))
						for (int p=0;mat[p]<=((1<<m)-1)&&p<=59;p++)
							if (((img[i-2]&mat[p])==0)&&((mat[p]&mat[k])==0)&&((mat[p]&mat[j])==0))
								{dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][p]+getbit(mat[j]));/*cout<<i<<" "<<mat[j]<<" "<<mat[k]<<" "<<dp[i][j][k]<<endl;*/}
	int ans=0;
	for (int i=0;mat[i]<=((1<<m)-1)&&i<=59;i++)
		for (int j=0;mat[j]<=((1<<m)-1)&&j<=59;j++)
			ans=max(dp[n][i][j],ans);
	cout<<ans<<endl;
	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