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

附上代码

Posted by phython at 2017-03-08 11:28:29 on Problem 1185
#include <cstdio>
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int N,M;
int map[105];
int state[1<<11];
int dp[105][1<<11][1<<11];
int cnt = 0;
int num(int x)
{
	int res = 0;
	while(x > 0)
	{
		if(x&1) res++;
		x >>= 1;
	}
	return res;
}
main()
{
	scanf("%d%d",&N,&M);
	for(int i = 0;i < N;i++)
	{
		for(int j = 0;j < M;j++)
		{
			char c;
			scanf(" %c",&c);
			if(c == 'H') map[i] |= 1<<(M-j-1);
		 } 
	}
	//第一步验证
	for(int S = 0;S < (1<<M);S++)
	{
		if((S&(S<<1)) || (S&(S<<2))) continue;
		state[cnt++] = S;
	}
	//初始化
	int res = 0;
	for(int i = 0;i < cnt;i++) 
		if(!(state[i]&map[0])) 
		{
			//printf("S:%d,num:%d\n",state[i],num(state[i])); 
			for(int j = 0;j < (1<<10);j++) 
			{
				dp[0][state[i]][j] = num(state[i]);
				res = max(res,num(state[i]));
			}
		}
	
	for(int i = 1;i < N;i++)
	{
		for(int j = 0;j < cnt;j++)
		{
			int S = state[j];
			if(S&map[i]) continue;
			for(int k = 0;k < cnt;k++)
			{
				int pS = state[k];
				if(pS & map[i-1]) continue;
				if(pS & S) continue;
				for(int q = 0;q < cnt;q++)
				{
					int ppS = state[q];	
					if(i >= 2 && (ppS&map[i-2])) continue;
					if(i >= 2 && ((ppS & pS) | (ppS & S))) continue;
					dp[i][S][pS] = max(dp[i][S][pS],dp[i-1][pS][ppS] + num(S));
					if(i == N-1) res = max(res,dp[i][S][pS]);
				}
			}
		}
	}
	cout<<res<<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