hust校赛c题 Move the Books（“最重上升子序列”）

题意是：给定一组整数，通过移动使这个序列变为递增的，移动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;
}

hust校赛c题 Move the Books（“最重上升子序列”）

原文：http://blog.csdn.net/u014664226/article/details/45920833