首页 > 代码库 > poj1351Number of Locks(记忆化搜索)
poj1351Number of Locks(记忆化搜索)
题目链接:
传送门
思路:
这道题是维基百科上面的记忆化搜索的例题。。。
四维状态dp[maxn][5][2][5]分别表示第几根棒子,这根棒子的高度,是否达到题目的要求和使用不同棒子数。那么接下来就是状态转移了。。。要用到位运算推断曾经是否这样的高度的棒子用到没。。。那么这个问题就攻克了。。。
题目:
Number of Locks
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 1126 | Accepted: 551 |
Description
In certain factory a kind of spring locks is manufactured. There are n slots (1 < n < 17, n is a natural number.) for each lock. The height of each slot may be any one of the 4 values in{1,2,3,4}( neglect unit ). Among the slots of a lock there are at least
one pair of neighboring slots with their difference of height equal to 3 and also there are at least 3 different height values of the slots for a lock. If a batch of locks is manufactured by taking all over the 4 values for slot height and meet the two limitations
above, find the number of the locks produced.
Input
There is one given data n (number of slots) on every line. At the end of all the input data is -1, which means the end of input.
Output
According to the input data, count the number of locks. Each output occupies one line. Its fore part is a repetition of the input data and then followed by a colon and a space. The last part of it is the number of the locks counted.
Sample Input
2 3 -1
Sample Output
2: 0 3: 8
Source
Xi‘an 2002
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#define New (1<<(d-1))
using namespace std;
const int maxn=17+10;
long long dp[maxn][5][2][5];
int n;
long long dfs(int ith,int height,int k,int use,int s)
{
if(dp[ith][height][k][use]!=-1)
return dp[ith][height][k][use];
if(ith==n)
{
if(k&&use>=3)
return 1;
else
return 0;
}
long long ans=0;
int tmp;
for(int d=1;d<=4;d++)
{
if(!(s&New))
tmp=use+1;
else
tmp=use;
// tmp=min(use,3);
if(k||(d*height==4&&d!=2))
ans=ans+dfs(ith+1,d,1,tmp,s|New);
else
ans=ans+dfs(ith+1,d,0,tmp,s|New);
}
return dp[ith][height][k][use]=ans;
}
int main()
{
while(~scanf("%d",&n))
{
if(n==-1) return -1;
printf("%d: ",n);
memset(dp,-1,sizeof(dp));
if(n<3)
puts("0");
else
{
dfs(0,0,0,0,0);
printf("%lld\n",dp[0][0][0][0]);
}
}
return 0;
}
poj1351Number of Locks(记忆化搜索)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。