UVA11212Editing aBook 编辑书稿

问题描述：你有一篇由n(n[2,9])个自然段组成的文章，希望将它们排列成1，2，、、、n。可以用Crtl+X和Ctrl+V快捷键来完成任务。每次可以剪一段连续的自然段，粘贴时按照顺序粘贴。注意，剪贴板只有一个，所以不能连续剪切两次，只能剪切和粘贴交替。

例如，为了将{2，4，1，5，3，6}变为升序，可以剪切1将其放到2前，然后剪切3将其放到4前，再如，对于排列{3，4，5，1，2}，只需要剪切一次和粘贴一次即可——将{3，4，5}放在{1，2}后面或者{1，2}放在{3，4，5}前面。

分析：对于长度n为9时，最多移动8次即可，而实验得知长度为9，{9，8，7，6，5，4，3，2，1}，最多移动5次。所以枚举移动上限为5。然后有一个最重要的剪枝，3d+h>3*maxd，d是目前移动的次数，也就是深度，而h是错误段落的个数，maxd是最大深度。可知每次移动最多会有3个段落次序发生改变，所以当错误段落个数大于剩余的移动次数*3的时候剪枝。

#include<cstdio> #include<cstring> #include<cctype> #include<queue> #include<iostream> #include<vector> using namespace std; const int maxn = 100 + 5; int a[maxn]; int n = 0; int h() {int cnt = 0;for (int i = 0; i < n - 1; i++)if (a[i] +1!= a[i + 1])cnt++;if (a[n - 1] != n)cnt++;return cnt; } bool is_sorted() {for (int i = 0; i < n - 1; i++)if (a[i] >= a[i + 1])return false;return true; } bool dfs(int d,int maxd) {if (3 * d + h() > 3 * maxd)return false;if (is_sorted())return true;int old[maxn], b[maxn];memcpy(old, a, sizeof(a));for (int i = 0; i < n; i++) {for (int j = i; j < n; j++) {int cnt = 0;for (int k = 0; k < n; k++)if (k<i || k>j)b[cnt++] = a[k];//取出不移动的位置for (int k = 0; k < cnt; k++) {//枚举剩余可移动位置（不移动的元素个数）int cnt2 = 0;for (int p = 0; p < k; p++)a[cnt2++] = b[p];//移动到这个位置for (int p = i; p <= j; p++)a[cnt2++] = old[p];for (int p = k; p < cnt; p++)a[cnt2++] = b[p];if (dfs(d + 1, maxd))return true;memcpy(a, old, sizeof(a));//回溯要还原}}}return false; } int solve() {if (is_sorted())return 0;int max_ans = 5;for (int maxd = 1; maxd < max_ans; maxd++) {if (dfs(0, maxd))return maxd;}return max_ans; } int main() {int kase=0;while (cin >> n &&n) {int temp;for (int i = 0; i < n; i++) { cin >> a[i]; }cout << "Case " << ++kase << ": ";cout << solve() << endl;}return 0; }

 

总结

以上是生活随笔为你收集整理的UVA11212Editing aBook 编辑书稿的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。