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

hihocoder1170(狀壓dp)

編輯:關於C++
題意:

小冰的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

 

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