Source Code

Problem: 1185  User: yzhw 
Memory: 820K  Time: 844MS 
Language: GCC  Result: Accepted 

Source Code 
# include <stdio.h>
# include <string.h>
char data[105][15];
int dp[2][59100];
int min(int a,int b)
{
	return a<b?a:b;
}
int max(int a,int b)
{
	return a>b?a:b;
}
void takenum(int num,int refer[],int bit)
{
	int i;
	for(i=1;i<=bit;i++)
	{
		refer[bit-i]=num%3;
		num/=3;
	}
}
int encode(int m,int temp[])
{
	int total=0;
	int i;
	for(i=0;i<m;i++)
	{
		total=total*3+(temp[i]?temp[i]-1:0);
	}
	return total;
} 

void search(int pos,int n,int m,int refer[],int oprice,int nprice)
{
	if(pos>=m)
	{
		int code=encode(m,refer);
		if(dp[n%2][code]<oprice+nprice)
			dp[n%2][code]=oprice+nprice;
	}
	else if(data[n][pos]=='H'||refer[pos]!=0)
		search(pos+1,n,m,refer,oprice,nprice);
	else
	{
		int i;
		search(pos+1,n,m,refer,oprice,nprice);
		
			refer[pos]=3;
		    search(pos+3,n,m,refer,oprice,nprice+1);
			refer[pos]=0;
		
	}
}
int main()
{
	int i,j,k,n,m,res=0;
	scanf("%d %d",&n,&m);
	memset(dp[0],0,sizeof(dp[0]));
	for(i=1;i<=n;i++)
		scanf("%s",data[i]);
	for(i=1;i<=n;i++)
	{
        memset(dp[i%2],0,sizeof(dp[i%2]));
		for(j=0;j<=59050;j++)
		{
			int status=j,price=dp[(i-1)%2][j];
			int temp[10];
			if(j!=0&&price==0) continue;		
			takenum(status,temp,m);
			search(0,i,m,temp,price,0);
		}
		//printf("OK\n");
	}
	for(i=1;i<=59050;i++)
		res=max(res,dp[n%2][i]);
	printf("%d\n",res);
	return 0;
}