求条啊

讨论

全局板块

// Problem:Luogu P1935 [国家集训队] 圈地计划

#include<bits/stdc++.h>
using namespace std;
const int MAXN=10;
int n,m,a[2][MAXN][MAXN],c[MAXN][MAXN];
int dp[MAXN][(1<<MAXN)];
int getbit(int zt,int i){return zt>>(m-i)&1;}
int getk(int zt,int i)
{
	bool l=0;
	if(i>1)l=getbit(zt,i)^getbit(zt,i+1);
	bool r=0;
	if(i<m)r=getbit(zt,i)^getbit(zt,i-1);
	return l+r;
}
int main()
{
	cin>>n>>m;
	for(int k=0;k<2;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				cin>>a[k][i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>c[i][j];
	for(int i=0;i<(1<<m);i++)
	{
		int sum=0;
		for(int j=1;j<=m;j++)
			sum+=a[getbit(i,j)][1][j]+c[1][j]*getk(i,j);
		dp[1][i]=sum;
	}
	for(int i=2;i<=n;i++)
		for(int A=0;A<(1<<m);A++)
			for(int B=0;B<(1<<m);B++)
			{
				int sum=0;
				for(int j=1;j<=n;j++)
				{
					int hk=getk(B,j);
					int lk=getbit(A,j)^getbit(B,j);
					dp[i-1][A]+=c[i-1][j]*lk;
					sum+=a[getbit(B,j)][i][j]+c[i][j]*(lk+hk);
				}
				dp[i][B]=dp[i-1][A]+sum;
			}
	int ans=0;
	for(int i=0;i<(1<<m);i++)
		ans=max(ans,dp[n][i]);
	cout<<ans;
	return 0;
}

的，洛谷只有最小割的解法，没有状压的……

j27eGU

2025-09-04 17:22:26

1.MAXN最大是10
2.getbit那个是求从左数第i位，应该右移m-i位
3.最小就是，相加的和最小也是0（吧）
以上都是蒟蒻的见解，我也不会额

2024-J-W010

2025-09-03 20:51:10

虽然样例没过，但是感觉很对（逃

/*
蒟蒻见解 qwq...

被注释的代码是原来的代码 qwq
*/

#include<bits/stdc++.h>
using namespace std;
//const int MAXN=10;
const int MAXN=101;
int n,m,a[2][MAXN][MAXN],c[MAXN][MAXN];
int dp[MAXN][(1<<MAXN)];
int getbit(int zt,int i){
	//return zt>>(m-i)&1;
	return (zt>>(i-1))&1;
}
int getk(int zt,int i)
{
//	bool l=0;
//	if(i>1)l=getbit(zt,i)^getbit(zt,i+1);
//	bool r=0;
//	if(i<m)r=getbit(zt,i)^getbit(zt,i-1);
//	return l+r;
	int res=0;
	if(i>1)
		res+=getbit(zt,i)^getbit(zt,i-1); // 左邻居
	if(i<m)
		res+=getbit(zt,i)^getbit(zt,i+1); // 右邻居
	return res;
	
}
int main()
{
	cin>>n>>m;
	for(int k=0;k<2;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				cin>>a[k][i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>c[i][j];
	for(int i=0;i<(1<<m);i++)
	{
		int sum=0;
		for(int j=1;j<=m;j++)
			sum+=a[getbit(i,j)][1][j]+c[1][j]*getk(i,j);
		dp[1][i]=sum;
	}
//	for(int i=2;i<=n;i++)
//		for(int A=0;A<(1<<m);A++)
//			for(int B=0;B<(1<<m);B++)
//			{
//				int sum=0;
//				for(int j=1;j<=n;j++)
//				{
//					int hk=getk(B,j);
//					int lk=getbit(A,j)^getbit(B,j);
//					dp[i-1][A]+=c[i-1][j]*lk;
//					sum+=a[getbit(B,j)][i][j]+c[i][j]*(lk+hk);
//				}
//				dp[i][B]=dp[i-1][A]+sum;
//			}
	for(int i=2;i<=n;i++){
		for(int B=0;B<(1<<m);B++){
			dp[i][B]=-1e9; // 初始化
			for(int A=0;A<(1<<m);A++){
				int sum=0;
				for(int j=1;j<=m;j++){
					int currbit=getbit(B,j); // 当前行的第 j 个
					sum+=a[currbit][i][j];
					sum+=c[i][j]*getk(B,j); // 水平差异
					sum+=c[i][j]*(getbit(A,j)!=currbit); // 如果上面不同，垂直差异
				}
				
				dp[i][B]=max(dp[i][B], dp[i-1][A]+sum);
			}
		}	
	}
	
	int ans=-1e9; // 极小值
	for(int i=0;i<(1<<m);i++)
		ans=max(ans,dp[n][i]);
	cout<<ans;
	return 0;
}

共 2 条回复