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

dp[i]表示以weight[i]

dp[i] = max(dp[i], dp[k] + weight[i]) (1 <= k <= i && weight[i] >= weight[k])

#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;
}

﻿﻿

## PKU2018校赛 H题 Safe Upper Bound

http://poj.openjudge.cn/practice/C18H 题目 算平均数用到公式$\bar{x}=\frac{x_1+x_2+x_3+\cdots+x_n}{n}$ 但如果用int型计算,那么$$x_1+x_2+x_3+\cdots+x_n$$可能会超过$$2^{31}-1$$ 算6个数的平均数可以这么算 Calculate the average of$$x_1,x_2,x_3$$$\bar{x}_1=\frac{x_1+x_2+x_3}{3}$Calculate t