西宁网站建设价格,东莞seo网站建设公司,wordpress图片资源主题,设计营销型网站域名思路
首先我们看看假设选中 mmm 个数后的答案。
我们首先现将 mmm 个数移动到一起#xff0c;在将他们重新排序。
我们知道#xff0c;mmm 个数移在一起时#xff0c;当位于中间的那个数不动时交换次数最少#xff0c;于是可以列出式子#xff08;cic_ici 是点 iii 的…思路
首先我们看看假设选中 mmm 个数后的答案。
我们首先现将 mmm 个数移动到一起在将他们重新排序。
我们知道mmm 个数移在一起时当位于中间的那个数不动时交换次数最少于是可以列出式子cic_ici 是点 iii 的位置
∑i1m∣cmidmid−cii∣\sum_{i 1}^m |c_{mid} mid - c_i i| i1∑m∣cmidmid−cii∣
我们可以将上面的式子改成如下形式
−2m∗midm%2∗cmid∑i1mci−1imid-\dfrac{2}{m}*mid m \% 2 * c_{mid} \sum_{i 1}^m c_i^{-1^{i mid}} −m2∗midm%2∗cmidi1∑mci−1imid
此时我们就可以用壮压DP来做了。
我们首先枚举每个数在枚举选上这个数后的情况在DP的过程中计算出下面的式子的求和公式里面的值前面的为常数并且在加上逆序对个数就可以了。
代码
#include bits/stdc.h
using namespace std;
int n, m, mid, a[205], f[205][1 18], INF 1e9;
int solve(int state, int i) {int sum 0, t 0, t1 0;//t是目前选了多少个数t1选了的树中比这个数要小的数。for (int j 0; j m; j) {if (state (1 j))t;if (a[i] - 1 j)t1 t;}return i * (t mid ? -1 : 1) i * (m 1) * (mid t) (t - t1);//此时的i就是c值于是我们把他带进去式子就可以了。
}
int main() {scanf(%d%d, n, m), mid (m 1) / 2;for (int i 1; i n; i) scanf(%d, a[i]);memset(f, 36, sizeof(f));for (int i 0; i n; i) f[i][0] 0;for (int i 1; i n; i)for (int j 0; j 1 m; j)f[i][j] min(j (1 (a[i] - 1)) ? f[i - 1][j ^ (1 (a[i] - 1))] solve(j, i) : INF, f[i - 1][j]);printf(%d, f[n][(1 m) - 1] - m / 2 * mid);return 0;
}
