1580. 切切蛋糕 - #include <Seter> - using namespace Orz;

1580. 切切蛋糕

Seter posted @ 2011年8月07日 12:23 in TYVJ with tags DP , 1901 阅读

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

 

记录号 Flag
记录信息
得分 / 耗时
程序提交时间
R544292 Accepted
From Seter
 P1580.c
100 / 0 ms
2011-8-7 11:17:17
R541647 Accepted
From Seter
 P1580.c
100 / 118 ms
2011-8-5 18:51:24

不得不说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;
}
By Seter

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee