Stacking Plates UVA - 1289

題目可使用動态規劃來求解。

分裂次數+合并次數-堆數-1 = 分裂次數*2-堆數-1

輸入完成後，首先導出盤子的所有直徑 d i a s dias dias（忽略重複的）和每個直徑的盤子所在的堆數 d i a _ n u m dia\_num dia_num，然後确定某個堆是否有某個直徑的盤子 s t a c k _ h a s _ d i a stack\_has\_dia stack_has_dia。

d p [ i ] [ j ] dp[i][j] dp[i][j]表示第 i i i直徑的所有盤子放置在第 j j j堆上的最小分裂數。

假設第 i − 1 i-1 i−1直徑的盤子已經安排好，且安排在了 k k k堆上，現在要安排第 i i i直徑的盤子。大方向是将所有第 i i i直徑的盤子移動到 j j j堆上，然後将 k k k堆的安排好的再移過來。這裡就有兩種情況：

1. j = = k j==k j==k

   即第 i − 1 i-1 i−1直徑的盤子已經安排在了 j j j堆上，接下來就要把其他的堆上的移動過來就行。接下來又要分兩種情況：

   1. 第 i i i直徑的盤子隻有一個，而且就在 j j j堆上

      這時候啥也不用做，此時的結果就是就等于 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i−1][j]

   2. 第 i i i直徑的盤子有多個，或者隻有一個但是不在 j j j堆上

      這時候就要把不在 j j j堆上的盤子 i i i移動過來。 （注意這樣的移動會造成 j j j堆拿起來再放回去，也就是分裂又合并，需要增加一個分裂次數）

2. j ! = k j != k j!=k

   這樣的情況是最常見也是最好解決的，将所有第 i − 1 i-1 i−1直徑的盤子移動過來即可。

   但是要注意這樣的移動會造成 j j j堆拿起來再放回去，也就是分裂又合并，需要增加一個分裂次數；并且可能 j j j堆和 k k k堆上存在第 i i i直徑的盤子，需要判斷一下然後減去相應的次數（因為相當于第 i i i直徑的盤子本來就在 j j j堆上不需要移動或者是和 k k k堆一起移動過來的）

從小到大枚舉 i i i，同時從小到大枚舉 j j j

然後枚舉 k k k 找到上述過程中的最小值，即為 d p [ i ] [ j ] dp[i][j] dp[i][j]。

最後在所有盤子安排好後（此時 i i i達到最大），枚舉 j j j找到最小值，即為最後的答案。以下為源代碼，代碼後提供一個更加簡單的思路。

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

const int MAX_STACK = 50 + 5;
const int MAX_DIA = 10000 + 5;
const int INF = 0x3f3f3f3f;

int dia_num[MAX_DIA];
int dp[MAX_DIA][MAX_STACK];
int stack_has_dia[MAX_STACK][MAX_DIA];
set<int> dias;

int solve()
{
	int stacks_num = 0, cases = 1;
	while(cin>>stacks_num){
		
		memset(dia_num, 0, sizeof(dia_num));
		memset(dp, 0, sizeof(dp));
		memset(stack_has_dia, 0, sizeof(stack_has_dia));
		dias.clear();
		int min_dia = MAX_STACK, max_dia = 0;

		for(int sta = 0; sta < stacks_num; sta++){
			
			int plates_num = 0;
			int dia_before = 0, dia_now = 0;

			cin>>plates_num;
			
			for(int plate = 0; plate < plates_num; plate++){
				
				cin>>dia_now;

				if(dia_now != dia_before){
					dia_before = dia_now;
					dias.insert(dia_now);
					dia_num[dia_now]++;
					stack_has_dia[sta][dia_now] = 1;
				}
			}
        }

		set<int>::iterator it = dias.begin(), it_now = dias.begin();

		it = dias.begin();

		for(int j = 0; j < stacks_num; j++){
			dp[*it][j] = dia_num[*it] - stack_has_dia[j][*it];
		}

		for(it_now = it++; it != dias.end(); it_now = it++){
			
			for(int j = 0; j < stacks_num; j++){
				
				int min_num = INF;
				
				for(int k = 0; k < stacks_num; k++){
					

					if(j == k){
						if((dia_num[*it] == 1) && (stack_has_dia[j][*it] == 1)){
							min_num = min(min_num, dp[*it_now][j]);
						}
						else{
							min_num = min(min_num, dp[*it_now][j] + dia_num[*it] + 1 - stack_has_dia[j][*it]);
						}
					}
					else{
						min_num = min(min_num, dp[*it_now][k] + dia_num[*it] + 1 - stack_has_dia[j][*it] - stack_has_dia[k][*it]);
					}
				}
				
				dp[*it][j] = min_num;
			}
		}
		
		int min_num = INF;

		for(int j = 0; j < stacks_num; j++){
			min_num = min(dp[*it_now][j], min_num);
		}

		printf("Case %d: %d\n", cases++, 2 * min_num - stacks_num + 1);
    }
	return 0;
}

int main()
{
    //streambuf * inbuf = cin.rdbuf((new ifstream("input.txt"))->rdbuf());//重定向，OJ時将它注釋掉
    //streambuf * outbuf = cout.rdbuf((new ofstream("output.txt"))->rdbuf());//重定向，OJ時将它注釋掉
    solve();
    return 0;
}
           

更簡單的思路參考自UVA 1289 Stacking Plates-dp。可以看出在枚舉 j j j時，已經有第 i i i直徑的盤子的 j j j堆一定比沒有的 j j j堆需要的分裂次數多。換句話說，其實我們可以在枚舉 j j j時，隻枚舉有第 i i i直徑的盤子的 j j j堆就行了，這樣就不需要枚舉所有的 j j j，以上的需要判斷的情況就會少一些。