程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> POJ 1351 Number of Locks (記憶化搜索 狀態壓縮)

POJ 1351 Number of Locks (記憶化搜索 狀態壓縮)

編輯:關於C++

 

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));
    }
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved