SPOJ 4053 - Card Sorting 最长不下降子序列

我们的男主现在手中有n*c张牌,其中有c(<=4)种颜色,每种颜色有n(<=100)张,现在他要排序,首先把相同的颜色的牌放在一起,颜色相同的按照序号从小到大排序。现在他想要让牌的移动次数最小,问移动的最小次数是多少。

【LIS】因为颜色种类相当少,可以枚举排序后颜色的次序。相同颜色的纸牌从小到大排序,所以所有纸牌的最终顺序也就确定了。

然后就是怎么样移动纸牌能够使纸牌成为最终的顺序。

因为从给定序到有序的移动次数等于从有序到给定序,所以我们反着想,对于有序的序列,移动一张纸牌,那么它的最长不降序列就减少1。如果移动多个呢,只要求出其中没有改变的最大长度即可,这个长度就是原序列的最长不降序列。

一般的,如果给定序的最长不降序列是x,那么到有序状态的移动次数一定是n*c-x

#include<bits/stdc++.h>
#define eps 1e-9
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define MAXN 1005
#define MAXM 40005
#define INF 0x3fffffff
using namespace std;
typedef long long LL;
struct node
{
int c,w,hash;
}p[]; int i,j,k,n,m,x,y,T,ans,big,cas,num,len;
bool flag;
int ord[],c;
bool vis[]; bool cmp(node a,node b)
{
return a.hash<b.hash;
} void work()
{
for (int i=;i<=n*c;i++)
{
p[i].hash=ord[p[i].c]*+p[i].w;//给每个元素一个唯一标识,按照这个标识来求最长不下降子序列
} int dp[],num;
dp[]=;
num=;
for (int i=;i<=n*c;i++)
{
if (p[i].hash>=dp[num])
{
dp[++num]=p[i].hash; }else
{
k=upper_bound(dp+,dp++num,p[i].hash)-dp;
dp[k]=p[i].hash;
}
} ans=min(ans,n*c-num);
} void dfs(int f)
{
for (int i=;i<=c;i++)
{
if (!vis[i])
{
vis[i]=;
ord[f]=i;
if (f==c) work();else dfs(f+);//枚举完毕后进入work()计算最长不下降子序列
vis[i]=;
}
}
} int main()
{
scanf("%d%d",&c,&n);
ans=INF;
for (i=;i<=c*n;i++)
{
scanf("%d%d",&p[i].c,&p[i].w);
}
memset(vis,,sizeof(vis));
dfs();//DFS枚举颜色次序
printf("%d\n",ans);
return ;
}
上一篇:C语言中函数和指针的參数传递


下一篇:【转】QT中QWidget、QDialog及QMainWindow的区别