题意是：给定一组整数，通过移动使这个序列变为递增的，移动i元素的话费为i
例如 2 2 5 3 4通过移动5使得序列变为2 2 3 4 5故最小花费为5，，如果移动3 4那么花费会为7
这道题可以通过求“最重上升子序列”来间接地得到结果，
dp[i]表示以weight[i]
为终点递增的最重的一系列书的重量之和。状态转移方程是
dp[i]=max(dp[i],dp[k]+weight[i])(1<=k<=i&&weight[i]>=weight[k])
所以最后的答案是sum（weight[i]）-max（dp[i]）
代码如下：
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<vector> #include<map> #include<queue> #include<stack> #include<string>#include<map> #include<set>using namespace std; #define LL long long //const int maxn = ;const int INF = 1000000000;//freopen("input.txt", "r", stdin);const int maxn = 100 + 5;int dp[maxn], weight[maxn];int sums, n;int main() {int test_case;scanf("%d", &test_case);while (test_case–) {scanf("%d", &n);sums = 0;for (int i = 1; i <= n; i++) {scanf("%d", &weight[i]);sums += weight[i];}for (int i = 1; i <= n; i++) {dp[i] = weight[i];for (int j = i – 1; j >= 1; j–) {if (weight[j] <= weight[i]) {dp[i] = max(dp[i], dp[j] + weight[i]);}}}int ans = 0;for (int i = 1; i <= n; i++) {if (dp[i] > ans) {ans = dp[i];}}printf("%d\n", sums – ans);}return 0;}
自信是一个人的胆，有了这个胆，你就会所向披靡！
