http://www.tyvj.cn:8080/Problem_Show.asp?id=1580

不得不说tyvj的机器很快。此题我用O(n2^(2m))的复杂度居然118ms……

呃……我觉得以前写的题解过于简单……所以找了道水题写攒RP！

攒RP的时候必须OrzWJMZBMR！

题目大意：给定n*m(n<=200,m<=10)的带权(|w|<=100)矩阵，取其中任意个不相邻不相交矩阵，使得权值最大。

观察到此题m小n大，直接往压位DP方面考虑：f[i][j]表示第i行以上，第i行状态为j能达到的最大值。

那么状态a能转移为状态b的条件是什么呢？

a中连续的1，在b中必须是连续的1或0。若在b中为1的话，则两端必须为0。

简化后得到：ab中不同的位置的左右两位如果都是1，则a无法转到b。

正推，即f[i][j]->f[i+1][k] j->k。时间复杂度O(n2^(2m))。观察到对于同一个状态j，可推出的k是一定的，所以可以开个表存（打表掉RP……）。跑了118MS。

#include <stdio.h>
int f[200][1024],a[200][100],n,m,map[1024][1024],s[1024];
__inline get(i,j){
	int k,ans=0;
	for(k=0;j>>k;k++)if(1<<k&j)ans+=a[i][k];
	return ans;
}int main(){
	int i,j,k,l,p,ans=0;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)for(j=0;j<m;j++)scanf("%d",a[i]+j);
	for(m=1<<m,i=0;i<m;i++)if(ans<(f[0][i]=get(0,i))&&n==1)ans=f[0][i];
	for(j=0;j<m;j++)for(k=j;k<m;k++){
		for(p=(l=j^k)&-l;l;p=(l-=p)&-l)if(p>>1&j&&p>>1&k||p<<1&j&&p<<1&k)break;
		if(!l)map[j][s[j]++]=k,map[k][s[k]++]=j;
	}for(i=1;i<n;i++)for(j=0;j<m;j++){
		for(p=get(i,j),k=0;k<s[j];k++)if(f[i][j]<f[i-1][map[j][k]]+p)f[i][j]=f[i-1][map[j][k]]+p;
		if(i==n-1&&ans<f[i][j])ans=f[i][j];
	}printf("%d\n",ans);
	return 0;
}

////////我自己感觉我写的判i是否可以推到j的if写的还行……呃……被虐了

继续观察……

其实和每一个点相关的就是这个点的八连通点！

所以可以用八王的方法！

f[i][j][k]表示i行j列状态k的最大值。其中状态k是i行中j列左边所有点（包括i行j列）和i-1行j列右边所有点（包括i-1行j列）的状态。

用f[i][j]推f[i][j+1](或f[i+1][0])的时候只需要看i行j列，i-1行j列，i-1行j+1列的状态就可以了……

这样写还不用写get……代码反而短了。但是草稿纸可能会多一点 - -

#include <stdio.h>
int f[200][10][2048],n,m,a[200][10],M,ans=0;
int main(){
	int i,j,k,K,X;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)for(j=0;j<m;j++)scanf("%d",a[i]+j);
	f[0][0][1]=a[0][0];M=1<<m+1;
	for(i=0;i<n;i++)for(j=0;j<m;j++)for(k=0;k<M;k++)if(j==m-1){
		if(i==n-1){if(ans<f[i][j][k])ans=f[i][j][k];continue;}
		if(f[i+1][0][K=k<<1&M-1]<f[i][j][k])f[i+1][0][K]=f[i][j][k];
		if(f[i+1][0][K^=1]<f[i][j][k]+a[i+1][0])f[i+1][0][K]=f[i][j][k]+a[i+1][0];
	}else{
		K=1<<j+1|k;
		if((X=k>>j&7)!=3&&X!=5&&X!=6&&f[i][j+1][K]<f[i][j][k]+a[i][j+1])f[i][j+1][K]=f[i][j][k]+a[i][j+1];
		if(X!=7&&f[i][j+1][K^=1<<j+1]<f[i][j][k])f[i][j+1][K]=f[i][j][k];
	}printf("%d\n",ans);
	return 0;
}

• inline
• block