Detail of message

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

投降的进来

Posted by donkeyinacm at 2009-11-27 20:50:49 on Problem 1185

//程序
//http://longzxr.blog.sohu.com/111314565.html
#include <iostream>
using namespace std;

#define MAXR 101
#define MAXS 64

int M[MAXR];
int DP[MAXR][MAXS][MAXS];
int S[MAXS];
int Cnt[MAXS];
int R,C,r,c,BR,mMaxl,Sp;



void Init()
{
	Sp=0;
	int temp;
	for(int i=0;i<(1<<C);i++)
	{
		temp=i;
		if((temp<<1)&i|(temp<<2)&i)
			continue;

		S[Sp++]=i;
		Cnt[Sp-1]=temp&1;
		while(temp=(temp>>1))
			Cnt[Sp-1]+=temp&1;

	}
}


void Input()
{
	

	cin>>R>>C;
	
		char HP;
		int Val;
		for(r=1;r<=R;r++)
		{
			Val=0;
			for(c=1;c<=C;c++)
			{
				cin>>HP;
				if(HP=='H')
					M[r]+=(1<<(C-c));

			}
		}
	

}

void DPF()
{
	int newMax;
	for(r=1;r<=R;r++)
		for(int i=0;i<Sp;i++)
			for(int j=0;j<Sp;j++)
				for(int k=0;k<Sp;k++)
				{
					newMax=0;
					if(S[i]&M[r])
						continue;
					if(S[i]&S[j])
						continue;
					if(S[i]&S[k])
						continue;

					if(DP[r][i][j]<DP[r-1][j][k]+Cnt[i])
						DP[r][i][j]=DP[r-1][j][k]+Cnt[i];
				}

}




void OutPut()
{
	int mMax=0;
	for(int i=0;i<MAXS;i++)
		for(int j=0;j<MAXS;j++)
			if(mMax<DP[R][i][j])
				mMax=DP[R][i][j];
	printf("%d\n",mMax);
}



int main()
{
	
	Input();
	Init();
	DPF();
	OutPut();
	return 0;
}


///////////////////////////////////////////////////////////////////////
//测试数据
100 10
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPHPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PHPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPHPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPHPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPHPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
(333)



99 9
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
PHHPHHPHH
HPHHPHHPH
HHPHHPHHP
(297)

Followed by:

Re:投降的进来 (32) haha132 2013-08-09 10:02:22

Post your reply here:

User ID:
Password:
Title:

Content:

> //程序
> //http://longzxr.blog.sohu.com/111314565.html
> #include <iostream>
> using namespace std;
> 
> #define MAXR 101
> #define MAXS 64
> 
> int M[MAXR];
> int DP[MAXR][MAXS][MAXS];
> int S[MAXS];
> int Cnt[MAXS];
> int R,C,r,c,BR,mMaxl,Sp;
> 
> 
> 
> void Init()
> {
> 	Sp=0;
> 	int temp;
> 	for(int i=0;i<(1<<C);i++)
> 	{
> 		temp=i;
> 		if((temp<<1)&i|(temp<<2)&i)
> 			continue;
> 
> 		S[Sp++]=i;
> 		Cnt[Sp-1]=temp&1;
> 		while(temp=(temp>>1))
> 			Cnt[Sp-1]+=temp&1;
> 
> 	}
> }
> 
> 
> void Input()
> {
> 	
> 
> 	cin>>R>>C;
> 	
> 		char HP;
> 		int Val;
> 		for(r=1;r<=R;r++)
> 		{
> 			Val=0;
> 			for(c=1;c<=C;c++)
> 			{
> 				cin>>HP;
> 				if(HP=='H')
> 					M[r]+=(1<<(C-c));
> 
> 			}
> 		}
> 	
> 
> }
> 
> void DPF()
> {
> 	int newMax;
> 	for(r=1;r<=R;r++)
> 		for(int i=0;i<Sp;i++)
> 			for(int j=0;j<Sp;j++)
> 				for(int k=0;k<Sp;k++)
> 				{
> 					newMax=0;
> 					if(S[i]&M[r])
> 						continue;
> 					if(S[i]&S[j])
> 						continue;
> 					if(S[i]&S[k])
> 						continue;
> 
> 					if(DP[r][i][j]<DP[r-1][j][k]+Cnt[i])
> 						DP[r][i][j]=DP[r-1][j][k]+Cnt[i];
> 				}
> 
> }
> 
> 
> 
> 
> void OutPut()
> {
> 	int mMax=0;
> 	for(int i=0;i<MAXS;i++)
> 		for(int j=0;j<MAXS;j++)
> 			if(mMax<DP[R][i][j])
> 				mMax=DP[R][i][j];
> 	printf("%d\n",mMax);
> }
> 
> 
> 
> int main()
> {
> 	
> 	Input();
> 	Init();
> 	DPF();
> 	OutPut();
> 	return 0;
> }
> 
> 
> ///////////////////////////////////////////////////////////////////////
> //测试数据
> 100 10
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPHPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PHPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPHPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPHPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPHPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> (333)
> 
> 
> 
> 99 9
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> PHHPHHPHH
> HPHHPHHPH
> HHPHHPHHP
> (297)
> 
> 
> 
>

Home Page Go Back To top