UVa 1289 Stacking Plates

题目

◇题目传送门◆（由于UVa较慢，这里提供一份vjudge的链接）
◇题目传送门◆

题目大意

有$N$堆盘子，第$i$堆盘子有$h_i$个，从上到下直径不减。有两种操作：

• split：将一堆盘子从某个位置分成上下两堆；
• join：将一堆盘子$a$放在另一堆盘子$b$上，要求$a$底部的盘子直径不超过$b$顶部盘子直径。

求将所有盘子叠成一堆的最少操作步数。

思路

仔细分析题目就会发现：最少操作步数=拆分次数+合并次数-N-1=拆分次数*2-N-1。

则该问题转化为求最少的拆分次数。

将盘子排序，大小相同的盘子视为同一盘子。

定义状态$f[i][j]$为到第$i$种盘子，这个盘子来自第$j$堆的最少拆分次数。

记$c(i)$为第$i$种盘子在所有盘子中的个数

则可枚举上一个盘子所在的堆$k$。若$k$可以放在第$i-1$种盘子的底部和第$i$种盘子的顶部，则$f[i][j]$可转移至$f[i-1][k]+c(i)-1$，否则转移至$f[i-1][k]+c(i)$。

注意$k$需要满足的条件：第$k$堆不仅需要拥有第$i-1$种盘子，且需要拥有第$i$种盘子。除非第$i$种盘子的来源只有$j$，否则必须满足$k\ne j$。

答案即为$f[M][i](1\le i\le N)$，其中MM<script type="math/tex" id="MathJax-Element-2729">M</script>为不同种类的盘子数量。

正解代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int Maxn=50;
const int Maxh=50;
const int INF=0x3f3f3f3f;int N,c,M;
int cnt[Maxn*Maxh+5];//记录第i种盘子出现次数
int f[Maxn*Maxh+5][Maxn+5];
int h[Maxn*Maxh+5][Maxn+5];//记录第i种盘子是否在第j堆出现
pair<int,int> A[Maxn*Maxh+5];//所有盘子，first记录直径，second记录来自第几堆void Prepare() {memset(cnt,0,sizeof cnt);memset(h,0,sizeof h);memset(f,0x3f,sizeof f);sort(A+1,A+c+1);c=unique(A+1,A+c+1)-A-1;//去掉相同盘子for(int i=1;i<=c;i++) {int p=i;M++;while(A[p].first==A[p+1].first&&p<c)p++;for(int j=i;j<=p;j++)h[M][A[j].second]=1;cnt[M]=p-i+1;i=p;}//处理出h数组及cnt数组
}int Solve() {for(int i=1;i<=N;i++)if(h[1][i])f[1][i]=cnt[1];//初始化，若第i堆有第1种盘子，则该状态赋值为cnt[1]，否则赋值为INFfor(int i=2;i<=M;i++)for(int j=1;j<=N;j++)if(h[i][j])//注意有这种盘子时才能尝试转移for(int k=1;k<=N;k++)if(h[i][k]&&(cnt[i]==1||k!=j))f[i][j]=min(f[i][j],f[i-1][k]+cnt[i]-1);else f[i][j]=min(f[i][j],f[i-1][k]+cnt[i]);int ret=INF;for(int i=1;i<=N;i++)ret=min(ret,f[M][i]);//找出最小拆分次数return ret*2-N-1;//返回答案
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifint cas=0;while(scanf("%d",&N)!=EOF) {c=M=0;for(int i=1;i<=N;i++) {int x;scanf("%d",&x);for(int j=1;j<=x;j++) {scanf("%d",&A[++c].first);A[c].second=i;}}Prepare();printf("Case %d: %d\n",++cas,Solve());}return 0;
}