【YNOI2019】排序
这道题实质上是求序列的最长不下降子序列
按照题意，我们要求出最小的代价，也就是说我们要让尽可能大的代价不动，也就是求出最长不下降子序列，之后用序列的和减去它即可。
#include <bits/stdc++.h> using namespace std; int T, n; int a[150], f[150], sum; int main() { scanf("%d", &T); while (T--) { sum = 0; scanf("%d", &n); for (register int i = 1; i <= n; ++i) { scanf("%d", &a[i]); sum += a[i]; } memset(f, 0, sizeof(f)); for (register int i = 1; i <= n; ++i) { for (register int j = 1; j < i; ++j) if (a[i] >= a[j]) f[i] = max(f[i], f[j]); f[i] += a[i]; } int maxx = 0; for (register int i = 1; i <= n; ++i) maxx = max(maxx, f[i]); printf("%d ", sum - maxx); } return 0; }