程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hihocoder1170（狀壓dp）

hihocoder1170（狀壓dp）

編輯：C++入門知識

hihocoder1170（狀壓dp）

題意：

小冰的N個機器人兄弟排成一列，每個機器人有一個顏色。現在小冰想讓同一顏色的機器人聚在一起，即任意兩個同顏色的機器人之間沒有其他顏色的的機器人。假設任意相鄰的兩個機器人可以交換位置，最少需要多少次交換？N<16，顏色種類不超過16種。

解法：一個明顯的結論是：交換機器人時，相同顏色的機器人不會發生交換（保持他們之間的相對順序）。即相當於給16種排序顏色。這總共有16！種結果，其dp方法雷同於旅行商問題的方法。

兩個代碼：

一種記憶化搜索，復雜度2^16*16*16：

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps 1e-8
#define zero(_) (abs(_)<=eps)
const double pi=acos(-1.0);
typedef long long LL;
const int Max=100010;
const LL INF=0x3FFFFFFFFFFFFFFF;
int a[Max];
LL num[20][20];
int sum[20];
LL ans[1<<17];
int n;
int k;
LL dfs(int state)
{
    if(ans[state]!=-1)
        return ans[state];
    ans[state]=INF;
    for(int i=0; i>t;
    int Case=1;
    while(t--)
    {
        memset(num,0,sizeof num);
        memset(sum,0,sizeof sum);
        memset(ans,-1,sizeof ans);
        scanf("%d%d",&n,&k);
        for(int i=0; i=0; i--)
        {
            for(int j=0; j

一種dp： 

復雜度2^16*16
 
/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps 1e-8
#define zero(_) (abs(_)<=eps)
const double pi=acos(-1.0);
typedef long long LL;
const int Max=100010;
const LL INF=0x3FFFFFFFFFFFFFFF;
int a[Max];
LL num[20][20];
int sum[20];
LL ans[1<<17];
LL tool[1<<16][16];
int re[1<<16];
int n;
int k;

int main()
{
    int t;
    cin>>t;
    int Case=1;
    for(int i=0; i<16; i++)
        re[1<=0; i--)
        {
            for(int j=0; j