方格取数（状压DP）

系统管理员 2022-05-28 07:55 233阅读 0赞

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int INF=0x3f3f3f3f;
    const int maxn=25;
    int n, num[maxn][maxn], sum[maxn][maxn], dp[maxn][maxn];
    int state[maxn], cnt=0;
    
    void init(){
    	for(int i=1; i<(1<<n); i++)
    	{
    		if((i&(i<<1))==0)//判断取的两个数是否相邻的方法
    		{
    			state[++cnt]=i;//保存状态
    			
    			for(int j=1; j<=n; j++)
    				for(int k=0; k<n; k++)
    						if((i>>k)&1)   sum[j][cnt]+=num[j][k+1];
    		}	
    	}
    }
    
    void solve(){
    	for(int j=1; j<=cnt; j++)
    		dp[1][j]=sum[1][j];
    	
    	for(int i=2; i<=n; i++)
    	{
    		for(int j=1; j<=cnt; j++)
    			for(int k=1; k<=cnt; k++)
    				if((state[j]&state[k])==0)
    					dp[i][j]=max(dp[i][j], dp[i-1][k] + sum[i][j]);//第i层j状态的状态转移方程
    	}
    	int mx=0;
    	for(int i=1; i<=cnt; i++)
    		mx=max(mx, dp[n][i]);
    	printf("%d\n", mx);
    	
    	return ;
    }
    
    int main(){
    	scanf("%d", &n);
    	
    	for(int i=1; i<=n; i++)
    		for(int j=1; j<=n; j++)
    			scanf("%d", &num[i][j]);
    	
    	init();
    	
    	solve();
    	
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，233人围观）

还没有评论，来说两句吧...

相关阅读

相关【状压DP】Most Powerful

[E-Most Powerful\_牛客竞赛动态规划专题班状压dp例题 (nowcoder.com)][E-Most Powerful_dp_ _nowcoder.com]

以你之姓@/ 2024年03月17日 08:58/ 0 赞/ 71 阅读

相关 group 状压dp

　　应某些人要求，我把标签删掉了　　这是一道好题。　　一看$c<=16$果断状压，但是怎么压？　　一个很显然的思路是，枚举上下两层的状态，每一层的状态极限有$C（c

逃离我推掉我的手/ 2023年08月17日 16:48/ 0 赞/ 138 阅读

相关 AcWing 1027. 方格取数（高难度线性dp）

本来想着先用dp获取最大值，然后标记，最后再dp一遍，貌似可以实现。正解：两条路线每次走的步数是一样的，k = i1 + j1 = i2 + j2 比较来自四个方位的点的

╰半夏微凉°/ 2022年08月28日 11:49/ 0 赞/ 143 阅读

相关 HDU3182-状压dp

Hamburger Magi Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K

川长思鸟来/ 2022年07月13日 14:56/ 0 赞/ 222 阅读

相关状压dp（瞎BB）

最近在写状压dp，写得不太顺利啊，抠很久才抠出来。可见如此之菜。状态压缩dp（简称状压dp）是一种非常典型的动态规划，通常使用在NP问题的小规模求解中，虽然是指数

迷南。/ 2022年06月17日 08:13/ 0 赞/ 242 阅读

相关 Hrbust 1214 方格取数（双线程dp）

题目链接： [Hrbust 1214][] 题解：双线程dp。设dp\[k\]\[i\]\[j\]，其中k表示走了k步，i表示第一个人在i 列，j表示第二个人在

柔光的暖阳◎/ 2022年06月14日 08:17/ 0 赞/ 151 阅读

相关方格取数（状压DP）

include<cstdio> include<iostream> include<algorithm> using namespace std

系统管理员/ 2022年05月28日 07:55/ 0 赞/ 234 阅读

相关 NOIP 2000 方格取数(多线程DP)

题目描述设有N\N的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）： ![pimg1026_1.jpg][] 某

末蓝、/ 2022年05月17日 10:38/ 0 赞/ 267 阅读

相关方格取数

题目描述设有N \\times NN×N的方格图(N \\le 9)(N≤9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字00。如下图所示（见样例）:

心已赠人/ 2022年03月07日 10:52/ 0 赞/ 352 阅读

相关 Problem Arrangement (状压DP)

Problem Arrangement [ZOJ - 3777 ][ZOJ - 3777] The 11th Zhejiang Provincial Collegiat

た入场券/ 2021年12月13日 01:35/ 0 赞/ 310 阅读