东莞寮步网站建设,上海网站建设备案号怎么恢复,企业建设网站的规定,seo顾问什么职位题目链接#xff1a;Editing a Book 题目描述#xff1a; 给定nnn个(1n10)1n10)1n10)数字#xff0c;数字分别是1,2,3,...,n1, 2, 3, ...,n1,2,3,...,n#xff0c;但是顺序是打乱的#xff0c;你可以选择一个索引区间的数字进行剪切操作。问最少进…题目链接Editing a Book 题目描述 给定nnn个(1n10)1n10)1n10)数字数字分别是1,2,3,...,n1, 2, 3, ...,n1,2,3,...,n但是顺序是打乱的你可以选择一个索引区间的数字进行剪切操作。问最少进行多少次剪切可以让这nnn个数字变成升序。 例如[1,2,4,3][1, 2, 4, 3][1,2,4,3]你可以选择剪切333然后在444的前面进行粘贴操作那么该操作算一次剪切操作序列变得升序。 题解 对于一个含有nnn个数字的序列要想让他变为升序最多只需要进行nnn次剪切操作一定能让序列升序即每次都选择未剪切过的最大的数字剪切到开头最多进行nnn次操作该序列一定变为有序。那么我们可以依次枚举[0−n][0-n][0−n]表示可能的答案每次进行暴力搜索如果某一次枚举的时候搜索成功那么此时枚举的次数就是最小的操作次数。这就是IDIDID算法IterativeDeepeningIterative DeepeningIterativeDeepening迭代深搜。因为直接搜索的话我们每次需要枚举区间以及移动的位置那么复杂度会达到(n3)depth(n ^3)^{depth}(n3)depth带入最大值999的话算出来的值接近6×10256\times 10^{25}6×1025很明显会超时。 那么我们需要使用剪枝如何进行剪枝呢由于数字都是1−n1-n1−n的那么我们可以记录每个数字的后一个数字不正确的个数即计算有多少个iii满足a[i]1]≠a[i1]a[i] 1] \ne a[i 1]a[i]1]a[i1]我们将这个数字记为cntcntcnt我们可以发现我们每一次剪切操作最多让cntcntcnt减少333。从下图我们可以看到如果我们进行一次剪切下图中是把part c移到到part b的前面后一个数字发生变化的位置有a的最后一个元素c的最后一个元素, b的最后一个元素。 也就是说在这种情况想最多只有三个数字的后一个元素会发生改变当然其他情况也是可以同理推出来的。所以每一次剪切操作最多能够让cntcntcnt减少333如果剩余的剪切操作在最优的情况下不能让cntcntcnt小于000那么此时就应该停止搜索即(maxDepth−nowDepth)∗3cnt(maxDepth - nowDepth) * 3 cnt(maxDepth−nowDepth)∗3cnt。这也就是AstarA\ starA star算法的思想三部分合起来就叫做IDA∗IDA*IDA∗。 实际上仅仅有上面的剪枝策略还是容易发生超时。而此时需要利用另外一种“贪心”策略连续的升序区间不应该被执行剪切操作也就是说对于一个序列里面类似于[2,3,4,5][2, 3, 4, 5][2,3,4,5]的序列只能作为整体操作而不应该只剪切其中的一部分。这似乎是显然的。 代码
#include bits/stdc.husing namespace std;int n, caseID 1;
vectorint number;int getCnt()
{int cnt 0;for (int i 0; i n - 1; i) {if (number[i] 1 ! number[i 1]) { cnt; }}return cnt;
}bool dfs(int nowDepth, int maxDepth)
{int cnt getCnt();if (nowDepth maxDepth) { return cnt 0; }if ((maxDepth - nowDepth) * 3 cnt) { return false; }for (int l 0; l n; l) {if (l - 1 0 number[l] - 1 number[l - 1]) { continue; }for (int r l; r n; r) { // 枚举需要移动的区间的左右端点if (r 1 n number[r] 1 number[r 1]) { continue; }for (int k r 2; k n; k) { // 枚举将区间移动到k前面vectorint temp(number);vectorint worker;for (int i 0; i k - 1; i) { // [0, k-1]移动if (l i i r) { continue; }worker.push_back(number[i]);}for (int i l; i r; i) { worker.push_back(number[i]); } // [l, r]移动for (int i k; i n; i) { worker.push_back(number[i]); } // 剩下部分移动number.swap(worker);if (dfs(nowDepth 1, maxDepth)) { return true; };number.swap(temp);}}}return false;
}int main()
{ios::sync_with_stdio(false);while(cin n n ! 0) {number.resize(n);for (int i 0; i n; i) { cin number[i]; }for (int maxDepth 0; ; maxDepth) {if (dfs(0, maxDepth)) {cout Case caseID : maxDepth endl;caseID;break;}}}return 0;
}
