Card Hand Sorting ，排列，状态压缩

Card Hand Sorting Kattis - cardhand

题意

将n张扑克牌排序，排序规则，不同花色之间的顺序没有要求，同意花色之间必须升序或者降序，问使得整个扑克牌排好序最少需要移动多少次

分析

知识点

组合数学，状态压缩，最长上升子序列 花色之间的排序 4! 4 ! 升序或者降序 24 2 4 共有 t=4!∗24 t = 4 ! ∗ 2 4 中情况，对于这t中情况，分别对每一中情况求LCS，求出LCS最长的就是要求的最有排列，因为这意味着，最长上升子序列中的元素不用移动

参考代码

#include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; template <class It> int LCS(It begin,It end)//求最长上升子序列的长度 { typedef typename iterator_traits <It>::value_type T; T inf = 1<<30; vector<T> Best(end-begin,inf); for(It i = begin ; i != end; ++i) *lower_bound(Best.begin(),Best.end(),*i) = *i; return lower_bound(Best.begin(),Best.end(),inf) - Best.begin(); } int main(void) { std::ios::sync_with_stdio(false); map<char,int> ma; ma['T'] = 10; ma['J'] = 11; ma['Q'] = 12; ma['K'] = 13; ma['A'] = 14; map<char,int> color; color['s'] = 0; color['h'] = 1; color['d'] = 2; color['c'] = 3; int n; char s[3]; int num[100]; int col[100]; int value[100]; while(cin>>n) { for(int i = 0; i < n; ++i) { cin>>s; if(ma.count(s[0])) num[i] = ma[s[0]]; else num[i] = s[0] - '0'; col[i] = color[s[1]]; } int ans = 0; int q[] = {0,1,2,3}; do { for(int dir = 0; dir < 16; ++dir)//2^4中升序降序的排列 { for(int i = 0; i < n; ++i) value[i] = q[col[i]] * 100 + num[i] * (1- 2*!!(dir&(1<<col[i])));//乘以二出现正负用来表示升序或者降序 ans = max(ans,LCS(value,value+n)); } } while(next_permutation(q,q+4));//4！种花色的排列 cout<<n-ans<<endl; } return 0; }