首页 > 代码库 > SRM627 Div2 1000 DP
SRM627 Div2 1000 DP
【题意】：
给出一个数列，可以进行的操作为最多能取K个互相不重叠的区间并将其反转，问经过操作以后，用冒号排序法排序数组所能达到的数的交
换次数的最小值。
例如：一个数列{7,2,2,13,5,5,2}最多可以取2个互相不重叠的区间，那么有[0,2],[3,6]，反转后的数组为{2,2,7,2,5,5,13}，用冒号排
序法排序时所需要的交换次数为3。
【知识点】：DP
【题解1】：
记忆化搜索DP（递归DP）
虽然我知道记忆化搜索这东西本身，但因为智商拙计经常用不上去，我觉得自己真的对编码本身还有待提高，下面通过几个步骤解析：
1、变量说明：
dp1[pos][rem]：代表从第pos到末尾这段数组内取了rem个不重叠子数组反转后用冒号排序法排序时所需要的最小交换次数。
dp2[pos][i]：区间[pos,i]经过反转后该区间内的数在经过对整个区间的冒号排序后所需要的最小交换次数。
dp1[pos][rem]、dp2[pos][i]初始均为-1，当这两个值不为-1时表示已经访问过，略过计算直接使用，其中dp1[pos][rem]所实现的即为记
忆化搜索。
2、状态转移方程：
dp1[pos][rem] = min(dp1[pos][rem], dfs(i + 1, rem - ((i == pos) ? 0 : 1)) + cur);
cur：代表[i,pos]的花费。当i==pos时不存在反转，故rem不变。
3、逻辑结构解析：
1）怎么实现连续区间不反转的？连续几次dfs都满足i == pos。
2）连续区间不反转且K的次数已用尽，剪枝：if(rem == 0 && i > pos) break;。
3）dfs终点：当pos超过数组尾端时，返回0。
【代码1】：
1 //type code which was others 2 3 #include <vector> 4 #include <cstring> 5 #define clr(abc,z) memset(abc,z,sizeof(abc)) 6 using namespace std; 7 const int inf = 1e9; 8 9 class BubbleSortWithReversals{10 public:11 vector<int> data;12 int dp1[55][55], dp2[55][55];13 int dfs(int pos, int rem){14 if(pos == data.size()) return 0;15 if(dp1[pos][rem] != -1) return dp1[pos][rem];16 dp1[pos][rem] = inf;17 for(int i = pos; i < data.size(); i++){18 if(rem == 0 && i > pos) break;19 int cur = 0;20 if(dp2[pos][i] != -1)21 cur = dp2[pos][i];22 else{23 for(int j = pos; j <= i; j++)24 for(int k = j + 1; k <= i; k++)25 if(data[j] < data[k]) cur++;26 for(int j = pos; j <= i; j++)27 for(int k = i + 1; k < data.size(); k++)28 if(data[j] > data[k]) cur++;29 dp2[pos][i] = cur;30 }31 dp1[pos][rem] = min(dp1[pos][rem], dfs(i + 1, rem - ((i == pos) ? 0 : 1)) + cur);32 }33 return dp1[pos][rem];34 }35 int getMinSwaps(vector <int> A, int K){36 clr(dp1, -1); clr(dp2, -1); data =http://www.mamicode.com/ A;37 return dfs(0, K);38 }39 };
【题解2】：
递推DP
1、变量说明：
f1[i][j]：[i,j]区间内的数不经反转在整个区间内进行冒号排序所需花费的交换次数。
f2[i][j]：[i,j]区间内的数经反转在整个区间内进行冒号排序所需花费的交换次数。
dp[i][j]：反转不大于j个不相交区间的前提下，[1, i]区间元素在整个区间内进行冒号排序所需花费的最小交换次数。
2、状态转移方程：
dp[i][j] = min(dp[i][j], dp[k][j] + f1[k + 1][i]);不反转情况
if(j) dp[i][j] = min(dp[i][j], dp[k][j - 1] + f2[k + 1][i]);可反转情况
3、逻辑结构解析：
1）clr(dp, 10); 初始值赋予最大值。
2）dp[0][0] = 0;状态转移的起点。
【代码2】：
1 //type code which was others 2 3 #include <vector> 4 #include <cstring> 5 #define clr(abc,z) memset(abc,z,sizeof(abc)) 6 using namespace std; 7 const int inf = 1e9; 8 9 class BubbleSortWithReversals{10 public:11 int n;12 int dp[110][110], A_[110];13 int f1[110][110], f2[110][110];14 int getMinSwaps(vector <int> A, int K){15 int n = A.size();16 for(int i = 1; i <= n; i++)17 A_[i] = A[i - 1];18 for(int i = 1; i <= n; i++)19 for(int j = i; j <= n; j++){20 for(int k = i; k <= j; k++)21 for(int p = k + 1; p <= j; p++)22 if(A_[k] > A_[p])23 f1[i][j]++;24 for(int k = i; k <= j; k++)25 for(int p = i; p < k; p++)26 if(A_[k] > A_[p])27 f2[i][j]++;28 for(int k = i; k <= j; k++)29 for(int p = j + 1; p <= n; p++)30 if(A_[k] > A_[p])31 f1[i][j]++, f2[i][j]++;32 }33 clr(dp, 10); dp[0][0] = 0;34 for(int i = 1; i <= n; i++)35 for(int j = 0; j <= K; j++)36 for(int k = 0; k < i; k++){37 dp[i][j] = min(dp[i][j], dp[k][j] + f1[k + 1][i]);38 if(j) dp[i][j] = min(dp[i][j], dp[k][j - 1] + f2[k + 1][i]);39 }40 int ans = 1e9;41 for(int i = 0; i <= K; i++)42 ans = min(ans, dp[n][i]);43 return ans;44 }45 };
【说明】：
这两个解法的代码均是比赛后参照他人的（基本属于对拍）。
现在在博客上写文章，我绝不会无意义地追求文章数量，我一定会尽力让自己的每一篇报告写得很细致。而且不足的地方以后回顾时会定
期维护，一定。