题目链接:http://poj.org/problem?id=2411
题目思路:状态压缩dp,貌似如果有多次询问相同,可以记录答案。。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
int n,m;
int i;
__int64 dp[12][1<<11];
int v[1<<11][1<<10];
int num[1<<11];
void dfs(int pos,int ps,int s)
{
if(pos==m)
{
v[ps][num[ps]++]=s;
return;
}
if(pos+2<=m&&(s&(1<<(pos+1)))==0&&(s&(1<<pos))==0)
dfs(pos+2,ps,s|(1<<(pos))|(1<<(pos+1)));
dfs(pos+1,ps,s);
}
int main()
{
int j,k;
while(scanf("%d%d",&n,&m),n|m)
{
memset(num,0,sizeof(num));
for(j=0;j<(1<<m);j++)
{
dfs(0,j,~j&((1<<m)-1));
}
for(i=0;i<=n;i++)
for(j=0;j<(1<<m);j++)
dp[i][j]=0;
dp[0][(1<<m)-1]=1;
for(i=1;i<=n;i++)
{
for(j=0;j<(1<<m);j++)
{
if(dp[i-1][j]==0)
continue;
for(k=0;k<num[j];k++)
dp[i][v[j][k]]+=dp[i-1][j];
}
}
printf("%I64d\n",dp[n][(1<<m)-1]);
}
}
分享到:
相关推荐
里面有非常详细的对于POJ 2411的解题报告,相信对于初学动态规划和深度优先搜索的同学来说有很好的帮助作用。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ2262-Goldbach's Conjecture 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ2388-Who's in the Middle 解题报告+AC代码
北大POJ2488-A Knight's Journey 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
POJ2528-Mayor's posters 测试数据。数据来源:Alberta Collegiate Programming Contest 2003.10.18 – 问题G
北大POJ1159-Palindrome 解题报告+AC代码
poj分类poj分类poj分类poj分类
poj-2528 Mayor's posters 测试数据及答案
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码