?
Number of Locks
| Time Limit: 1000MS |
? |
Memory Limit: 10000K |
| Total Submissions: 1161 |
? |
Accepted: 571 |
?
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
题目链接：http://poj.org/problem?id=1351
题目大意：用数字1，2，3，4求一个长度为n的序列，要求这个序列中至少有三个不同的数字且至少有一组相邻的值相差3，求满足条件的序列的个数
题目分析：dp[num][t][ok][last]表示当前序列长度为num，用了t种数字，若有有相邻的1，4则ok为1，否则为0，last表示当前序列的最后一个数，采用记忆化搜索，DFS里除了dp的4个值还要多一个参数st，用2进制表示当前数字的使用状态，例如st＝1111表示四个数都用了，每次将搜索的数与当前状态与一下来判断使用个数有没有增加.
#include
#include
#define ll long long ll dp[20][5][2][5]; int n; ll DFS(int num, int t, int ok, int last, int st) { if(num == n) { if(t >= 3 && ok) return 1; else return 0; } if(dp[num][t][ok][last] != -1) return dp[num][t][ok][last]; ll tmp = 0; for(int i = 1; i <= 4; i++) { int tt, ok2 = 0, curst = 1 << (i - 1); if((i == 1 && last == 4) || (i == 4 && last == 1)) ok2 = 1; if(st & curst) tt = t; else tt = t + 1; if(tt > 3) tt = 3; tmp += DFS(num + 1, tt, ok || ok2, i, st | curst); } return dp[num][t][ok][last] = tmp; } int main() { while(scanf("%d", &n) != EOF && n != -1) { memset(dp, -1, sizeof(dp)); printf("%d: %lld\n", n, DFS(0, 0, 0, 0, 0)); } }