东莞seo网站建设公司,常熟市住房和城乡建设局网站,现在网站尺寸,南王科技：美方裁定公司思路
首先我们看看假设选中 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;
}
