80pts求助
查看原帖
80pts求助
983912
Linzijun_0607楼主2024/7/31 17:24
#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;
int n,m;
int num[105][105],dp[55][1<<10][1<<10],dp2[55][1<<10][1<<10];
int sum[1<<10][100];
inline int __count(int awa){
	int sum=0;
	while(awa){
		awa-=lowbit(awa);
		sum++;
	}
	return sum;
}
signed main(){
	cin>>n>>m;
	memset(dp,0x3f,sizeof dp);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>num[i][j];
	for(int i=1;i<=n;i++)
		for(int j=0;j<(1<<m);j++)
			for(int k=1;k<=m;k++)
				if(j&(1<<(k-1))) sum[i][j]+=num[i][k];
	for(int i=0;i<(1<<m);i++) dp[1][i][0]=sum[1][i],dp2[1][i][0]=__count(i);
	for(int i=2;i<=n;i++){
		for(int j=0;j<(1<<m);j++){
			for(int k=0;k<(1<<m);k++){
				for(int l=0;l<(1<<m);l++){
					if(((j|k|l|k<<1|k>>1)&(1<<m)-1)==((1<<m)-1)) {
						int a1=dp[i-1][k][l]+sum[i][j],a2=dp2[i-1][k][l]+__count(j);
						if(dp[i][j][k]>a1||dp2[i][j][k]>a2&&dp[i][j][k]==a1) dp2[i][j][k]=a2,dp[i][j][k]=a1;		
					}
				}
			}
		}
	}
	int ans1=0x3f3f3f3f,ans2=0x3f3f3f3f;
	for(int i=0;i<(1<<m);i++){
		for(int j=0;j<(1<<m);j++){
			if(((j|i|i<<1|i>>1)&(1<<m)-1)==((1<<m)-1)) 
			if (ans1>dp[n][i][j]||dp[n][i][j]==ans1&&dp2[n][i][j]<ans2)
				ans1=dp[n][i][j], ans2=dp2[n][i][j];
		}
	}
	printf("%d %d\n",ans2,ans1);
}
2024/7/31 17:24
加载中...