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

自认为还可以的代码 AC的哦。。

Posted by pengshihui at 2010-06-12 23:56:42 on Problem 1185
#include "stdio.h"
#include "memory.h"
int map[102];
int possible[60],N,M,t,length[60],dp[60][60][102];

int main(void)
{
	t=0;
	int i,k,j,l,max;
	char c;
	scanf("%d%d",&N,&M);
	scanf("\n");
	map[0]=map[1]=0;
	memset(dp,-1,sizeof(dp));
	for(i=0;i!=N;++i)
	{
		for(j=0;j!=M;++j)
			if(scanf("%c",&c)==1&&c=='P')
				map[i+2]+=1<<(M-j-1);
		scanf("%c",&c);
	}
	k=1<<M;
	for(i=0;i!=k;++i)
		if(!(i>>1&i||i>>2&i))
			possible[t++]=i;
	for(i=0;i!=t;++i)
	{
		k=0;
		for(j=0;j!=M;++j)
			if(possible[i]&(1<<j))
				k++;
		length[i]=k;
	}
	dp[0][0][1]=0;
	for(i=1;i!=N+1;++i)
	{
		for(j=0;j!=t;++j)
		{
			if((possible[j]&map[i])!=possible[j]) continue;
			for(k=0;k!=t;++k)
			{
				max=0;
				if((possible[k]&map[i+1])!=possible[k]||possible[j]&possible[k]) continue;
				for(l=0;l!=t;++l)
				{
					if((possible[l]&map[i-1])!=possible[l]||possible[j]&possible[l]||possible[k]&possible[l]) continue;
					max=dp[l][j][i]>max?dp[l][j][i]:max;
				}
				dp[j][k][i+1]=max+length[k];
			}
		}
	}
	max=0;
	for(i=0;i!=t;++i)
		for(j=0;j!=t;++j)
			max=max<dp[i][j][N+1]?dp[i][j][N+1]:max;
		printf("%d\n",max);
	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