主题:关于动态规划状态压缩。reply+30分!
efforttoc
[专家分:200] 发布于 2006-09-29 21:49:00
状态压缩怎么实现?
这是一道要用到状态压缩的题目,http://acm.pku.edu.cn/JudgeOnline/problem?id=1185,怎么实现呢?
回复+30分!thx in advance
回复列表 (共2个回复)
沙发
bigchen [专家分:1940] 发布于 2006-10-28 17:59:00
动规我没有学
但是状态压缩好像可以用哈夫曼树的方法!
板凳
steven215 [专家分:0] 发布于 2008-12-09 21:55:00
pku 1185 炮兵阵地 状态压缩DP
2007年11月15日 星期四 19:20
n分析一个列为10(M的最大值)的表。注意到一个全为P的空列上一共也只有60种合法的Cannon放置方法。具体对一个列数为10的PH表而言,对每一列也只有前两列对其产生影响,因此我们可以用一个二维数组cal [lm] [lm]来记录其上一行处于第x种状态,该行自身出于第y种状态时,从首行扫描到该行时所能存放的最多cannon数。其中lm是列数为M时一列的所有可能合法放置方法,x、y在0到lm-1之间。
Pre[60][60],now[60][60]
对新行进行扫描时
for(i=0;i<lm;i++)for(j=0;j<lm;j++)
for(k=0;k<lm;k++){
如果当前行,前一行,前二行分别是第i,j,k个状态,并且都能够相容。而now [j] [i]<pre [k] [j]+第i个状态新增的cannon数。那么更新now [j] [i]。
}
#include "stdio.h"
#include "memory.h"
inline void SetBit(int& a,int i){ a|=(1<< (i-1));}
int state[60];
int stateNum[1024];
char staterow[1024][101];
char statestate[1024][1024];
void Initialize();
void Input();
int pre[60][60],now[60][60];
int N,M;
char map[101][11];
int IsValidateRows(int state,int row);
int IsValidateStates(int state1,int state2);
int getNum(int state);
int maxNum=0;
int maxState;
int main(int argc, char* argv[])
{
Input();
Initialize();
int i,j,k;
for(i=0;i<maxState;++i)
for(j=0;j<maxState;++j)
{
if( IsValidateRows(state[i],0) && IsValidateRows(state[j],1)
&& IsValidateStates(state[i],state[j]) )
pre[i][j]=getNum(state[i])+getNum(state[j]);
else
pre[i][j]=0;
if(maxNum<pre[i][j]) maxNum=pre[i][j];
}
for(int l=2;l<=N ;++l)
{
for(i=0;i<maxState;++i)
{
if(staterow[state[i]][l-2 ]==0 || IsValidateRows(state[i],l-2)== 0 ) continue;
for(j=0;j<maxState;++j)
{
if( staterow[state[j]][l-1 ]==0 || statestate[ state[i] ][ state[j] ] == 0
|| IsValidateRows(state[j],l-1)==0 || IsValidateStates(state[i],state[j]) == 0
) continue;
for(k=0;k<maxState;++k)
{
if( staterow[state[k]][l ]==0 || IsValidateRows(state[k],l)==0
|| statestate[ state[i] ][ state[k] ] == 0 || IsValidateStates(state[i],state[k])==0
|| statestate[ state[j] ][ state[k] ] == 0 || IsValidateStates(state[j],state[k])==0
) continue;
int t=pre[i][j]+getNum(state[k]);
if(now[j][k]<t) now[j][k]=t;
if(maxNum<now[j][k]) maxNum=now[j][k];
}
}
}
memcpy(pre,now,sizeof(now));
memset(now,0,sizeof(now));
}
printf("%d\n",maxNum);
return 0;
}
void Initialize()
{
int i,j,k;
memset(state,0,sizeof(state));
memset(stateNum,-1,sizeof(stateNum));
memset(staterow,-1,sizeof(staterow));
memset(statestate,-1,sizeof(statestate));
for(i=1;i<=M;i++)
SetBit(state[i],i);
int index=M;
for(i=1;i<=M;++i)
for(j=i+3;j<=M;++j)
{
++index;
SetBit(state[index],i);
SetBit(state[index],j);
}
for(i=1;i<=M;++i)
for(j=i+3;j<=M;++j)
for(k=j+3;k<=M;++k)
{
++index;
SetBit(state[index],i);
SetBit(state[index],j);
SetBit(state[index],k);
}
if(M == 10)
{
++index;
SetBit(state[index],1);
SetBit(state[index],4);
SetBit(state[index],7);
SetBit(state[index],10);
}
maxState=index+1;
}
void Input()
{
int i;
scanf("%d %d ",&N,&M);
for(i=1;i<=N;++i)
scanf("%s",map[i]);
for(i=0;i<M;i++)
map[0][i]='H';
map[0][i]=0;
}
int getNum(int s)
{
int k=s;
if(stateNum[s] == -1)
{
int n=0;
while (k)
{
n++;
k=k&(k-1);
}
stateNum[s]=n;
}
return stateNum[s];
}
int IsValidateRows(int s,int row)
{
int k=s;
if((int)staterow[s][row] == -1)
{
int j = M ;
while(k)
{
int num = k % 2;
k /= 2;
-- j;
if ( num && map[row][j]=='H' )
{
staterow[s][row]=0;
return 0;
}
}
staterow[s][row]=1;
}
return staterow[s][row];
}
int IsValidateStates(int state1,int state2)
{
int s1=state1,s2=state2;
if((int)statestate[s1][s2] == -1)
{
int num1,num2;
while (state1 && state2)
{
num1 = state1 % 2;
num2 = state2 % 2;
if( num1== 1 && num2 ==1)
{
statestate[s1][s2]=0;
break;
}
state1 /= 2;
state2 /= 2;
}
if(statestate[s1][s2]==-1)
statestate[s1][s2]=1;
}
return statestate[s1][s2];
}
我来回复