疑问发生了,数据水了?
查看原帖
疑问发生了,数据水了?
550940
yty2010楼主2024/6/7 21:22

在我第一次学对拍时(10分钟前)发现我的代码AC了,但是每次对拍超不过十个数据就WA了,那么我的AC代码错哪里了?

my code:

#include<bits/stdc++.h>
using namespace std;
int n,m;
int dp[5][1030][1030];  
int p,s[1030],sum[1030];
char mp[105][15];
int mp1[105];
bool dis[1030][1030];
int maxn;
void init()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>mp[i][j];
			mp1[i]=mp1[i]*2+(mp[i][j]=='P'?1:0);
		}
	}
	for(int i=0;i<(1<<m);i++)
	{
		if((i&(i<<1))||(i&(i<<2)))
			continue;
		bool q=0;
		int k=0;
		for(int j=m;j>=0;j--)
		{
			if((i>>(m-j))&1)
			{
				k++;
			}
		}
		if(q==1)
			continue;
		s[++p]=i;
		sum[p]=k;
	}
	for(int i=1;i<=p;i++)
	{
		for(int j=1;j<=p;j++)
		{
			for(int k=0;k<=n;k++)
			{
				if((s[i]>>k)&1==1&&(s[j]>>k)&1==1)
				{
					dis[i][j]=dis[j][i]=1;
					break;
				} 
			}
		}
	}
}
void dfs()
{
	for(int i=1;i<=p;i++)
	{
		bool q=0;
		for(int k=0;k<=n;k++)
		{
			if(!((mp1[1]>>k)&1)&&(s[i]>>k)&1)
			{
				q=1;
				break;
			}
		}
		if(q==1)
			continue;
		dp[1][i][1]=sum[i];
		maxn=max(maxn,dp[1][i][1]);
	}
	
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=p;j++)
		{
			bool q=0;
			for(int k=0;k<=n;k++)
			{
				if(!((mp1[i]>>k)&1)&&(s[j]>>k)&1)
				{
					q=1;
					break;
				}
			}
			if(q==1)
				continue;
			for(int k=1;k<=p;k++)
			{
				if(dis[j][k]==1)
					continue;
				for(int l=1;l<=p;l++)
				{
					if(dis[j][l]==1)
						continue;
					dp[i%3][j][k]=max(dp[(i-1)%3][k][l]+sum[j],dp[i%3][j][k]);
					maxn=max(maxn,dp[i%3][j][k]);
					
				}
			}
		}
	}
	cout<<maxn;
}
int main()
{
	freopen("data.in","r",stdin);
	freopen("data2.out","w",stdout); 
	init();
//	for(int i=1;i<=n;i++)
//	{
//		cout<<mp1[i]<<endl;
//	}
//	cout<<endl;
//	for(int i=1;i<=p;i++)
//	{
//		cout<<s[i]<<' '<<sum[i]<<endl; 
//	}
//	cout<<endl;
//	for(int i=1;i<=p;i++)
//	{
//		for(int j=i+1;j<=p;j++)
//		{
//			cout<<dis[i][j]<<' ';
//		}
//		cout<<endl;
//	}
	dfs();
}
2024/6/7 21:22
加载中...