Problem Description
给你一个n*n的格子的棋盘,每个格子里面有一个非负数。
从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取的数所在的2个格子不能相邻,并且取出的数的和最大。
从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取的数所在的2个格子不能相邻,并且取出的数的和最大。
Input
包括多个测试实例,每个测试实例包括一个整数n 和n*n个非负数(n<=20)
Output
对于每个测试实例,输出可能取得的最大的和
Sample Input
3 75 15 21 75 15 28 34 70 5
Sample Output
188
Author
ailyanlu
Source
Recommend
8600
话说Lvsi小盆友挂了套比赛,然后名字叫“来虐我啊”,之后把链接发过来了……瞄了一眼,大多都是dp题,所以顺手做了,能不能虐他再说了……
这题很简单,只需要把满足条件的全部筛出来,然后按照相邻两行dp就可以了,典型的状态压缩dp,没什么讲的……只是坑爹的是算复杂度老感觉要挂,所以加了个cnt数组……
附上代码
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int map[22][22]; int av[50000]; int dp[22][50000]; int cnt[22][50000]; int main() { int i,j,n,up,k,s; up=0; for (i=0;i<(1<<20);i++) { if ((i & (i<<1))!=0 || (i & (i>>1))!=0) continue; av[up++]=i; } while(scanf("%d",&n)!=EOF) { memset(dp,0,sizeof(dp)); for (i=0;i<n;i++) { for (j=0;j<n;j++) { scanf("%d",&map[i][j]); } } for (i=0;i<n;i++) { for (j=0;j<up && av[j]<(1<<n);j++) { cnt[i][j]=0; for (k=0;k<n;k++) { if ((av[j] & (1<<k))!=0) cnt[i][j]+=map[i][k]; } // printf("%d %d %d\n",i,av[j],cnt[i][j]); } } for (i=0;i<up && av[i]<(1<<n);i++) { dp[0][i]=cnt[0][i]; } for (i=1;i<n;i++) { for (j=0;j<up && av[j]<(1<<n);j++) { for (k=0;k<up && av[k]<(1<<n);k++) { if ((av[j] & av[k])!=0) continue; dp[i][k]=max(dp[i][k],cnt[i][k]+dp[i-1][j]); } } } s=0; for (i=0;i<up && av[i]<(1<<n);i++) { s=max(s,dp[n-1][i]); } printf("%d\n",s); } return 0; }