题解：P13792 [SWERC 2023] Card game

linzongyi_520 · 2025-10-27 19:20:54 · 题解

题目链接

题目大意

有五种花色的牌，分别为银色 S，白色 W，绿色 E，红色 R，还有一个更加高级的青色 C。每种花色有 N 张牌，我们的手里也有 N 张牌。现在我们需要让同一花色的所有牌按递增顺序相邻排列，并且青色牌要放在末尾（同样按递增顺序排列）。

思路分析

• 核心：将求最少操作次数转换为求最长上升子序列

  对于无需移动的牌，它们已经构成了符合要求的序列，因此不需要移动。对于需要移动的牌，我们需要把它放到符合要求的序列中。

• 考虑 “贪心 + 二分” 优化

  我们可以用一个 dp 数组来维护上升子序列的最小结尾。dp 的每个元素是 优先级，牌编号其结尾的优先级和编号尽可能小。这样可以让后续更多牌能满足“优先级非递减 + 数字递增”，从而加入子序列。
  对于每张新牌，通过二分查找 dp 中第一个“不满足条件”的位置（即优先级 > 当前牌，或优先级相等但编号 \ge 当前牌），将新牌插入或替换该位置，确保 dp 始终维持最小结尾的特性。

• 整体思路

  1. 读入 N 和手中的 N 张牌，将花色转为编码，存入数组。
  2. 建立 SWER 的初始排列，再用 get_len 计算该排列下的上升子序列长度，更新最大值。
  3. 枚举剩余 23 种排列，对于每种排列：
     先用 pos 数组更新优先级，再用 get_len 计算当前排列的上升子序列长度，更新最大值。
  4. 最后用总牌数减去上升子序列的最大值即为最小操作次数。

     AC Code

     不要抄袭

     
     #include<bits/stdc++.h>
     using namespace std;

int N; int pos[4]; vector<pair<int,int>> card; vector<int> a={0,1,2,3};//记录四种颜色的位置，转换为优先值
int max_len=INT_MIN;

int get_len() { vector<pair<int,int>> dp; //遍历每一张卡片 for(int i=0;i<card.size();i++) { int color=card[i].first;//当前卡片的颜色
int num=card[i].second;//当前卡片的编号

    //计算当前卡片对应的优先级p：
    //若为'C'，p固定为4，其他颜色则使用其在当前排列中的位置pos[color]
    int p=(color == 4) ? 4 : pos[color];

    int l=0,r=dp.size();
    while(l < r)
    {
        int mid=l+(r-l)/2;
        if(dp[mid].first > p || (dp[mid].first == p && dp[mid].second >= num))
            r=mid;
        else
            l=mid+1;
    }
    if(l == dp.size())
        dp.emplace_back(p,num);
    else
        dp[l]={p,num};
}
//返回在当前颜色排列下上升子序列的长度 
return dp.size();

}

int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

cin >> N;

for(int i=0;i<N;i++)
{
    string s;
    cin >> s;
    int color;
    if(s[0] == 'S')
        color=0;
    else if(s[0] == 'W')
        color=1;
    else if(s[0] == 'E')
        color=2;
    else if(s[0] == 'R')
        color=3;
    else//'C'
        color=4;
    int num=stoi(s.substr(1));
    card.emplace_back(color,num);
}

//处理初始排列 
for(int i=0;i<4;i++)
    pos[a[i]]=i;
max_len=max(max_len,get_len());

//处理剩余排列 
while(next_permutation(a.begin(),a.end()))
{
    for(int i=0;i<4;i++)
        pos[a[i]]=i;
    max_len=max(max_len,get_len());
}

cout << N-max_len;

return 0;

}