跪求大佬帮忙
查看原帖
跪求大佬帮忙
47205
jzy_go楼主2020/8/23 10:03

蒟蒻刚学c++一分钟,求助大佬,实在不会了(哭

#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+(ch-'0');
		ch=getchar();
	}
	return x*f;
}
int n,m;
struct node{
	int num;
	int a[1001];
}a[1001];
int w[1001][1001];
int f[1001][1001];
void chuli(int x,int y)
{
	for(int j=0;j<(1<<m);j++)
	{
		if((j&(j<<1))||(j&(j>>1))||(j&y)||(j&(j<<2))||(j&(j>>2)))
		continue;
		a[x].num++;
		a[x].a[a[x].num]=j;
	}
}
int main()
{
	n=read();
	m=read();
	int x;
	char ch;
	for(int i=1;i<=n;i++)
	{
		int y=0;
		for(int j=1;j<=m;j++)
		{
			ch=getchar();
			if(ch=='H')
			x=0;
			else
			x=1;
			y=y*2+1-x;
		}
		chuli(i,y);
		ch=getchar();
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=a[i].num;j++)
		{
			int kk=a[i].a[j];
			while(kk)
			{
				if(kk&1)
				w[i][j]++;
				kk=kk>>1;
			}
		}
	}
	for(int j=1;j<=a[2].num;j++)
	{
		for(int k=1;k<=a[1].num;k++)
		{
			if(a[2].a[j]&a[1].a[k])
			continue;
			f[2][j]=max(f[2][j],f[1][k]+w[2][j]);
		}
	}
	for(int i=3;i<=n;i++)
	{
		for(int j=1;j<=a[i].num;j++)
		{
			for(int k=1;k<=a[i-1].num;k++)
			if(a[i].a[j]&a[i-1].a[k])
				continue;
			else
			for(int o=1;o<=a[i-2].num;o++)
			{
				if((a[i].a[j]&a[i-2].a[o])||(a[i-1].a[k]&a[i-2].a[o]))
				continue;
				f[i][j]=max(f[i][j],f[i-1][k]+f[i-2][o]+w[i][j]);
			}
		}
	}
	int ans=0;
	for(int j=1;j<=a[n].num;j++)
	{
		ans=max(ans,f[n][j]);
	}
	cout<<ans<<endl;
	return 0;
}

2020/8/23 10:03
加载中...