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

想明白了，很轻松的就能AC,266ms(附代码)

Posted by hataksumo at 2012-08-05 20:04:40 on Problem 1185

/*这题关键就是对状态的理解，由于每个炮能打2格的位置
我们可以先dfs出，每一行可能摆放的各种炮兵状态，canState[],canNum[]
经预先计算得出，m=10时最大的状态数为60
其次，没放过一行时，该行有两个有意义的状态。
一个是当前行的状态，一个是他上一行的状态。
这样一来，每一行就有60*60种状态。
我们可以定义dp[l][i][j],l表示第几层,i表示当前层的状态,j表示上一层的状态
那么 dp[l][i][j] = max{dp[l-1][j][k]} + canNum[i]
canNum[i]表示dfs预处理得出的第i个状态对应的编号
剩下的，就跟背包的更新极为类似了。
*/


#include<cstdio>
#include<cstring>

#define compatible(a,b) (((a)&(b))==0)
#define MN 110
#define MS 61
#define MM 11


/*dfs函数和它用到的全局变量
dfs函数，用于打表出每行m个位置时
各种可行的状态,数字为为1表示是炮*/
int canState[MS];
int canNum[MS];
int len;
int hillp;
void dfs(int loc,int num,int m);
/******************************/
/*input函数和它用到的全局变量
此函数功能为，输入数据，并处理
得到各层的hill,数位为1表示此位置不能放炮*/
char coteau[MN][MM];
int hill[MN];
void input(int n,int m);
/*****************************/
/*dpSolve函数和它所用到的全局变量
该函数功能是利用动态规划，计算出各层
各状态中，最多能放多少炮*/
int dpAmount[MN][MS][MS];
bool dpVisit[MN][MS];
void dpSolve(int n,int m);
/*************************/
int findmx(int n);//查找dpAmount中的最大值
int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		input(n,m);
		dpSolve(n,m);
		printf("%d\n",findmx(n));
	}
	return 0;
}
void input(int n,int m)
{
	int i,tmp;
	char *p;
	hill[0] = -2;
	for(i=1;i<=n;i++)
	{
		scanf("%s",coteau[i]);
		tmp = 0;
		for(p=coteau[i];*p;p++)
		{
			tmp<<=1;
			if(*p=='H')
				tmp|=1;
		}
		hill[i]=tmp;
	}
}


void dfs(int loc,int num,int m)
{
	int i;
	canNum[len] = num;
	canState[len++]=hillp;
	if(loc>=m-3)
	{
		return;
	}
	for(i=loc+3;i<m;i++)
	{
		hillp|=(1<<i);
		dfs(i,num+1,m);
		hillp&=(~(1<<i));
	}
}


void dpSolve(int n,int m)
{
	int i,j,k,l,mx;
	//初始化dp所需的各元素
	len=hillp=0;
	dfs(-3,0,m);
	memset(dpAmount,-1,sizeof(dpAmount));
	memset(dpVisit,false,sizeof(dpVisit));
	dpAmount[0][0][0] = 0;dpVisit[0][0]=true;
	//进行dp
	for(l=1;l<=n;l++)
	{
		for(i=0;i<len;i++)
		{
			if(compatible(canState[i],hill[l]))
			{
				for(j=0;j<len;j++)
				{
					if((!compatible(canState[i],canState[j]))||
						(!dpVisit[l-1][j]))continue;
					mx=-1;
					for(k=0;k<len;k++)
					{
						if(dpAmount[l-1][j][k]>=0&&
							compatible(canState[i],canState[k])&&
							mx<dpAmount[l-1][j][k])
						{
							mx = dpAmount[l-1][j][k]; 
						}
					}
					if(mx>=0)
					{
						dpAmount[l][i][j] = canNum[i] + mx;
						dpVisit[l][i] = true;
					}
				}
			}
		}
	}
}
int findmx(int n)
{
	int mx=0;
	int i,j,l;
	for(l=1;l<=n;l++)
	{
		for(i=0;i<len;i++)
		{
			for(j=0;j<len;j++)
			{
				if(mx<dpAmount[l][i][j])
					mx = dpAmount[l][i][j];
			}
		}
	}
	return mx;
}
/*
5 4
PHPP
PPHH
PPPP
PHPP
PHHP


80 10
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH


6
216
*/

Followed by:

Post your reply here:

User ID:
Password:
Title:

Content:

> /*这题关键就是对状态的理解，由于每个炮能打2格的位置
> 我们可以先dfs出，每一行可能摆放的各种炮兵状态，canState[],canNum[]
> 经预先计算得出，m=10时最大的状态数为60
> 其次，没放过一行时，该行有两个有意义的状态。
> 一个是当前行的状态，一个是他上一行的状态。
> 这样一来，每一行就有60*60种状态。
> 我们可以定义dp[l][i][j],l表示第几层,i表示当前层的状态,j表示上一层的状态
> 那么 dp[l][i][j] = max{dp[l-1][j][k]} + canNum[i]
> canNum[i]表示dfs预处理得出的第i个状态对应的编号
> 剩下的，就跟背包的更新极为类似了。
> */
> 
> 
> #include<cstdio>
> #include<cstring>
> 
> #define compatible(a,b) (((a)&(b))==0)
> #define MN 110
> #define MS 61
> #define MM 11
> 
> 
> /*dfs函数和它用到的全局变量
> dfs函数，用于打表出每行m个位置时
> 各种可行的状态,数字为为1表示是炮*/
> int canState[MS];
> int canNum[MS];
> int len;
> int hillp;
> void dfs(int loc,int num,int m);
> /******************************/
> /*input函数和它用到的全局变量
> 此函数功能为，输入数据，并处理
> 得到各层的hill,数位为1表示此位置不能放炮*/
> char coteau[MN][MM];
> int hill[MN];
> void input(int n,int m);
> /*****************************/
> /*dpSolve函数和它所用到的全局变量
> 该函数功能是利用动态规划，计算出各层
> 各状态中，最多能放多少炮*/
> int dpAmount[MN][MS][MS];
> bool dpVisit[MN][MS];
> void dpSolve(int n,int m);
> /*************************/
> int findmx(int n);//查找dpAmount中的最大值
> int main()
> {
> 	int n,m;
> 	while(~scanf("%d%d",&n,&m))
> 	{
> 		input(n,m);
> 		dpSolve(n,m);
> 		printf("%d\n",findmx(n));
> 	}
> 	return 0;
> }
> void input(int n,int m)
> {
> 	int i,tmp;
> 	char *p;
> 	hill[0] = -2;
> 	for(i=1;i<=n;i++)
> 	{
> 		scanf("%s",coteau[i]);
> 		tmp = 0;
> 		for(p=coteau[i];*p;p++)
> 		{
> 			tmp<<=1;
> 			if(*p=='H')
> 				tmp|=1;
> 		}
> 		hill[i]=tmp;
> 	}
> }
> 
> 
> void dfs(int loc,int num,int m)
> {
> 	int i;
> 	canNum[len] = num;
> 	canState[len++]=hillp;
> 	if(loc>=m-3)
> 	{
> 		return;
> 	}
> 	for(i=loc+3;i<m;i++)
> 	{
> 		hillp|=(1<<i);
> 		dfs(i,num+1,m);
> 		hillp&=(~(1<<i));
> 	}
> }
> 
> 
> void dpSolve(int n,int m)
> {
> 	int i,j,k,l,mx;
> 	//初始化dp所需的各元素
> 	len=hillp=0;
> 	dfs(-3,0,m);
> 	memset(dpAmount,-1,sizeof(dpAmount));
> 	memset(dpVisit,false,sizeof(dpVisit));
> 	dpAmount[0][0][0] = 0;dpVisit[0][0]=true;
> 	//进行dp
> 	for(l=1;l<=n;l++)
> 	{
> 		for(i=0;i<len;i++)
> 		{
> 			if(compatible(canState[i],hill[l]))
> 			{
> 				for(j=0;j<len;j++)
> 				{
> 					if((!compatible(canState[i],canState[j]))||
> 						(!dpVisit[l-1][j]))continue;
> 					mx=-1;
> 					for(k=0;k<len;k++)
> 					{
> 						if(dpAmount[l-1][j][k]>=0&&
> 							compatible(canState[i],canState[k])&&
> 							mx<dpAmount[l-1][j][k])
> 						{
> 							mx = dpAmount[l-1][j][k]; 
> 						}
> 					}
> 					if(mx>=0)
> 					{
> 						dpAmount[l][i][j] = canNum[i] + mx;
> 						dpVisit[l][i] = true;
> 					}
> 				}
> 			}
> 		}
> 	}
> }
> int findmx(int n)
> {
> 	int mx=0;
> 	int i,j,l;
> 	for(l=1;l<=n;l++)
> 	{
> 		for(i=0;i<len;i++)
> 		{
> 			for(j=0;j<len;j++)
> 			{
> 				if(mx<dpAmount[l][i][j])
> 					mx = dpAmount[l][i][j];
> 			}
> 		}
> 	}
> 	return mx;
> }
> /*
> 5 4
> PHPP
> PPHH
> PPPP
> PHPP
> PHHP
> 
> 
> 80 10
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> HHHHHHHHHH
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> HHHHHHHHHH
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> HHHHHHHHHH
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> HHHHHHHHHH
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> HHHHHHHHHH
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> HHHHHHHHHH
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> HHHHHHHHHH
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> HHHHHHHHHH
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> HHHHHHHHHH
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> HHHHHHHHHH
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> HHHHHHHHHH
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> HHHHHHHHHH
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> HHHHHHHHHH
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> HHHHHHHHHH
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> HHHHHHHHHH
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> PPPPPPPPPP
> HHHHHHHHHH
> 
> 
> 6
> 216
> */

Home Page Go Back To top