poj 2411 新写法

别以为我在刷水题。。。。

今天做了场srm，500pt想到了是dp但是无从下手，但是看了rng_58的神代码后顿觉海阔天空啊（盯着看了一个下午），相比于一年前的写法，真的是不忍直视啊，

TC真是个好地方。。。赞！

其实就是将普通的铺砖块问题用类似于插头dp逐格递推的思路来写。下面的代码相信大家应该都能看懂。

#include <cstdio>

#include <cstring>

#include <algorithm>

long long dp[2][1<<11];

int main() {

    int n , m;

    while(scanf("%d%d",&n,&m),n||m) {

      int cur = 0 , nxt = 1;

      dp[cur][0] =  1;

       for(int i = 0; i < n; i++) {

          for(int j = 0; j < m; j++) {

            memset(dp[nxt],0,sizeof(dp[nxt]));

            for(int s = 0; s < (1<<m); s++) if(dp[cur][s]){

                if(s&1){dp[nxt][s>>1] += dp[cur][s];continue;}

                if(j+1<m && !(s&2) ){

                    int mask = ( s | 2 ) >> 1;

                    dp[nxt][mask] += dp[cur][s];

                }

                if(i+1<n) {

                    int mask = (s | (1<<m)) >> 1;

                    dp[nxt][mask] += dp[cur][s];

                }

            }

            std::swap(cur,nxt);

          }

       }

       printf("%I64d\n",dp[cur][0]);

    }

    return 0;

}

下面是一年前的写法。。。

#include<stdio.h>

#include<string.h>

int h,w;

__int64 dp[15][2050];

void dfs1(int row,int state,int col,int state2){

	if(col>w) return ;

	if(col==w) {

		dp[row+1][state2]+=dp[row][state];

		return ;

	}

	if(!(state&(1<<col))) dfs1(row,state,col+1,state2+(1<<col));

	else dfs1(row,state,col+1,state2);

}

void dfs2(int row,int state,int col,int state2){

	if(col>w) return ;

	if(col==w) {

		if(state2!=state)

		   dp[row][state2]+=dp[row][state];

		return ;

	}

	if(!(state&(1<<col)) &&	!(state&(1<<(col+1))))

		dfs2(row,state,col+2,state2+(1<<col) + (1<<(col+1)));

	dfs2(row,state,col+1,state2);

}

void gao(){

	int i,j;

	dp[0][(1<<w)-1]=1;

	for(i=0;i<h;i++){

          for(j=0;j<(1<<w);j++)

			  if(dp[i][j])

				  dfs1(i,j,0,0);

		  for(j=(1<<w)-1;j>=0;j--)

		      if(dp[i+1][j])

				  dfs2(i+1,j,0,j);

	}

}

int main(){

	while(scanf("%d%d",&h,&w)!=EOF && h+w){

		int temp;

		if(h<w){

			temp=h;h=w;w=temp;

		}

		memset(dp,0,sizeof(dp));

		gao();

		printf("%I64d\n",dp[h][(1<<w)-1]);

	}

	return 0;

}

巴特西

poj 2411 新写法

最新文章

热门文章