求助大佬,帮我看一下,连样例都过不了
查看原帖
求助大佬,帮我看一下,连样例都过不了
355521
rainbow_star楼主2021/10/20 09:26
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
ll n,m;
ll mapp[101];//(0是从左边开始的)压缩地图,mapp[i]压缩第i行,平原是 0,山丘是1
ll dp[5000][5000][3];
//滚动数组,dp[L][S]表示:上一行的状态是 L,当前状态是 S
ll summ[5000];//summ[i]状态i中有几个1
char c; 
ll maxx;
ll answer;
ll getsum(ll x) //计算出所有状态下的summ 
{
	ll ans=0;
	while(x!=0)
	{
		if(x&1==1)
			ans++;
		x>>=1;
	}
	return ans;
}
int main()
{
//	freopen("pbzd.in","r",stdin); 
	ll i,j,k,l;
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=n;i++)
	{
		getchar();
		for(j=0;j<m;j++)
		{
			c=getchar();
			if(c=='H')
				mapp[i]+=1<<j;
		}
	}
	maxx=(1<<m)-1;
	for(i=0;i<=maxx;i++)
		summ[i]=getsum(i);
	for(i=1;i<=n;i++)//当前正在计算第几行的dp值 
	{
		for(j=0;j<=maxx;j++)//枚举上一行状态
		{
			//判断是否放在了山丘上
			if(j&mapp[i-1]!=0) 
				continue;
			//判断每个状态有没有两个炮兵左右距离在两格之内
			if(j&(j<<1)!=0||j&(j<<2)!=0||j&(j>>1)!=0||j&(j>>2)!=0)
				continue;
			for(k=0;k<=maxx;k++)//枚举这一行状态
			{
				//判断是否放在了山丘上
				if(k&mapp[i]!=0) 
					continue;
				//判断每个状态有没有两个炮兵左右距离在两格之内
				if(k&(k<<1)!=0||k&(k<<2)!=0||k&(k>>1)!=0||k&(k>>2)!=0)
					continue;
				//判断每一列与上一行有没有炮兵在对应位置上 
				if(j&k!=0)
					continue;
				for(l=0;l<=maxx;l++)//枚举上上行的状态 
				{
					//判断每一列与上上行有没有炮兵在对应位置上 
					if(k&l!=0||j&l!=0)
						continue;
					//判断是否放在了山丘上
					if(l&mapp[i-2]!=0&&i!=1) 
						continue;
					//判断每个状态有没有两个炮兵左右距离在两格之内
					if(l&(l<<1)!=0||l&(l<<2)!=0||l&(l>>1)!=0||l&(l>>2)!=0)
						continue;
					dp[j][k][2]=max(dp[j][k][2],dp[l][j][1]+summ[k]);
//					answer=max(dp[j][k][2],answer);
				}
			}
		}
		for(j=0;j<=maxx;j++)//枚举上一行状态
			for(k=0;k<=maxx;k++)//枚举这一行状态
			{
				cout<<j<<" "<<k<<" "<<dp[j][k][2]<<endl; 
				dp[j][k][1]=dp[j][k][2];
				dp[j][k][2]=summ[k];
			}
	}
	for(j=0;j<=maxx;j++)//枚举上一行状态
			for(k=0;k<=maxx;k++)//枚举这一行状态
				answer=max(answer,dp[j][k][1]);
	printf("%lld",answer);
	return 0;
}
2021/10/20 09:26
加载中...