Card Hand Sorting Gym - 101550C（枚举+LIS）

本文主要是介绍Card Hand Sorting Gym - 101550C（枚举+LIS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
n个卡牌，每个卡牌有值和种类，你可以任意调换某张卡牌的顺序，要求使得每个种类的卡牌在一起，且为有序（递增或递减）

思路：
枚举属性的顺序以及是递增还是递减。
然后寻找与原串的LIS。LIS代表最大不需要改变的部分。

#include <cstdio>
#include <cstring>
#include <vector>
#include <map>using namespace std;
typedef long long ll;const int INF = 0x3f3f3f3f;
int n;
map<char,int>mp;
struct Node {int val;int dat;int id;int v;
}a[105];int dp[105];int cmp(Node a1,Node a2) {if(a1.v == a2.v) return a1.val < a2.val;return a1.v < a2.v;
}void init() {for(int i = 2;i <= 9;i++) {mp['0' + i] = i;}mp['T'] = 10;mp['J'] = 11;mp['Q'] = 12;mp['K'] = 13;mp['A'] = 14;mp['s'] = 0;mp['h'] = 1;mp['d'] = 2;mp['c'] = 3;
}int DP() {memset(dp,0,sizeof(dp));int res = 0;dp[1] = 1;for(int i = 2;i <= n;i++) {dp[i] = 1;for(int j = 1;j < i;j++) {if(a[i].id > a[j].id)dp[i] = max(dp[i],dp[j] + 1);}res = max(res,dp[i]);}return res;
}int main() {scanf("%d",&n);for(int i = 1;i <= n;i++) {char s[10];scanf("%s",s);a[i].val = mp[s[0]];a[i].dat = mp[s[1]];a[i].id = i;}int arr[10] = {0,1,2,3};int ans = INF;do {for(int i = 0;i < (1 << 4);i++) {for(int j = 1;j <= n;j++) {a[j].v = arr[a[j].dat];if(i & (1 << a[j].v)) {a[j].val = abs(a[j].val) * -1;}else {a[j].val = abs(a[j].val);}sort(a + 1,a + 1 + n,cmp);ans = min(ans,n - DP());}}}while(next_permutation(arr,arr + 4));
}

这篇关于Card Hand Sorting Gym - 101550C（枚举+LIS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---