UVA 1289 Stacking Plates——dp

UVA 1289 Stacking Plates——dp

拿到这道题目第一反应就是它很像汉诺塔问题，只是多了划分这个操作，因此第一步我们尝试把它简化成汉诺塔问题

首先明确一点，最终结果等于划分次数加合并次数。设划分次数为x，那么划分x次必然会形成n+x个堆，把这n+x个堆合并成1个堆需要n+x-1次合并操作，因此最终结果就是2*x+n-1,这样我们只用划分次数x就表示出了最终结果。不过为了使问题更接近汉诺塔问题，我们应该用合并次数来表示最终结果，设合并次数为y，根据上面的推理y=n+x-1，最终结果就是2*y-n+1

然后开始dp，首先把所有盘子从小到大排个序，然后按直径离散化一下，dp【i】【j】表示把前i种盘子放到堆j的最小花费，那么dp【i】【j】一定是由dp【i-1】【k】（1<=k<=n）转移而来的，分析一下会发现转移的时候要讨论j！=k和j=k两种情况。当j！=k时，大方向上要把所有堆中种类为i的盘子合并到堆j，然后把堆k上的（1~i-1）种盘子合并到堆j（注意堆k中可能有种类为i的盘子，这种情况下就不用单独移动（1~i-1）种盘子了）；当j=k时，大方向上也是要把所有堆中种类为i的盘子合并到堆j，然后把堆j上的（1~i-1）种盘子合并到堆j（可以理解为先要把（1~i-1）种盘子拿起来，然后把所有种类为i的盘子放过来，最后再把（1~i-1）中盘子合并上），但是如果只有堆j中有种类为i的盘子，那么应该什么也不做，这样才是最优的。具体细节推荐自己实现，或者参考我的代码。

如果你发现按照上面所说的写情况很多，思路很乱，可以试试这个优化，即我们可以在dp的过程中使用贪心思想来简化状态总数。考虑这一点，当你在放第i种盘子时，你要进行决策，即把第i种盘子合并到哪个堆里，而分析后会发现最优情况一定是把第i中盘子放在【有第i种盘子】的那些堆中，比如说堆【3 4】、【5 6】、【3 5】，你在移动第3种盘子（即数字3）的时候一定是把它移动到第一堆或者第三堆，移动到第二堆一定不是最优的，有了这个优化再写代码思路就会非常清晰了

#include #include #include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;int kase, n, id[10005], vis[55][2505], dp[2505][55];//id[i]为盘子直径i离散化后的值, vis[i][j]判断堆i中是否出现过第j种盘子, dp[i][j]表示把前i种盘子排好放到堆j的最小花费vector plates[55];//输入数据set val;//用于离散化vector heap[2505];//heap[i]表示第i种盘子对应的堆set::iterator it;void init() {//初始化 memset(dp, INF, sizeof(dp)); memset(vis, false, sizeof(vis)); for (int i = 1; i <= n; i++) plates[i].clear(); val.clear(); for (int i = 1; i <= 2500; i++) heap[i].clear();}int discrete() {//离散化 int ran = 0; for (it = val.begin(); it != val.end(); it++) id[*it] = ++ran; return ran;}int main() { while (~scanf("%d", &n)) { init(); int k, x; for (int i = 1; i <= n; i++) { scanf("%d", &k); while (k--) { scanf("%d", &x); plates[i].push_back(x); val.insert(x); } } int ran = discrete(); for (int i = 1; i <= n; i++) { for (int j = 0; j < plates[i].size(); j++) { x = id[plates[i][j]]; if (!vis[i][x]) { vis[i][x] = 1; heap[x].push_back(i);//保证第x种盘子对应的堆不重复 } } } for (int i = 0; i < heap[1].size(); i++) dp[1][heap[1][i]] = heap[1].size()-1; for (int i = 2; i <= ran; i++) { for (int a = 0; a < heap[i].size(); a++) { for (int b = 0; b < heap[i-1].size(); b++) { int j = heap[i][a], k = heap[i-1][b], cnt = heap[i].size(); if (j == k) dp[i][j] = min(dp[i][j], dp[i-1][j]+(cnt==1?0:cnt));//cnt-1==0?0:cnt-1+1 else dp[i][j] = min(dp[i][j], dp[i-1][k]+cnt-1+!vis[k][i]); } } } int ans = INF; for (int i = 0; i < heap[ran].size(); i++) ans = min(ans, dp[ran][heap[ran][i]]); printf("Case %d: %d\n", ++kase, 2*ans-n+1); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。