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



时间: 05-20

hust校赛c题 Move the Books(“最重上升子序列”)的相关文章

hust校赛 f题 The tree of hust(lis 变形)

题目大意是给出一段数字序列,可以忽略一次一段连续的序列,求忽略后的最长连续上升子序列 思路是dp,用end数组记录以当前元素作为结尾的最长连续上升序列的元素个数,那么不难得到状态转移方程为 dp(i) = max(dp(i - 1),  max( end[k] ) ) + 1 代码如下: #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostr

hust校赛d题 PHP is the best language int the world(二分图着色+递推)

题目大意是给出一个图,要求判断是否是二分图,如果是,求二分图两个节点集之差的最小值. 两个人如果不会争吵的话连一条边,形成一个图,取这个图的反图.这个反图之间存在边则 说明这两个人不能在同一个team.首先二分染色看是否能够将反图变成一个二分图. 如果能染成二分图,记录每个二分图颜色人数.在某个联通分量里白色/黑色可以交换. 接下来用dp[i][j] = 1表示前i个联通分量能够形成一个人数为j的team. 然后在dp[num][s]里面遍历找到相差最小的team分法,输出答案,num为联通分量

CSU 1425 NUDT校赛 I题 Prime Summation

这个题本来有希望在比赛里面出了的 当时也想着用递推 因为后面的数明显是由前面的推过来的 但是在计算的时候 因为判重的问题 ...很无语.我打算用一个tot[i]来存i的总种树,tot[i]+=tot[j]//j为可以由j推到i的一系列数,但这样是不对的,会产生大量重复计算... 看了下标程才发现要用二维来计算出种类总数,f[i][j]+=sum(f[i-j][k]) 表示在推i数的时候,第一个素数为j的种类数,注意j一定为素数,而且k不能大于j...标程里面处理的比较简练,就学了下他的写法. 至

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

2018WFU校赛B题

我们在ACM的题目中已经了解了什么是ACM了,ACM还是很残酷的了(? _ ?),那么现在你就要解决一个ACM最简单的题了,简单到省赛和区域赛都不会出这种简单的题.ls很强,即使每年都在ACM这个大坑里,但是他依旧关心自己的排名.但是排名规则真的很令人烦恼,因为它是按平均分排的并且他们学习的科目数量是不一定的.所以你的任务就来了,ls的班里有n名同学,每个同学有3门课程,现在你要根据他们的成绩总和从大到小排名如果成绩相同则按他们名字的字典序(字典序当然就是字典的顺序啦)排名. Input 第1行

2018 FJUT acm校赛 b题 第二集:以后我就叫你小蛤了

第二集:以后我就叫你小蛤了 TimeLimit:1000MS  MemoryLimit:128MB 64-bit integer IO format:%lld Problem Description "小蛤啊,对了以后我就叫你小蛤了,你给的题完全没有难度啊" "哼,你别得意,让你碰巧做出来了而已,接下来这题你绝对不可能做出来的,你要是做出来了balabalabala...." "行了行了,快说题目吧,我时间宝贵啊!" 小A心急如焚,想尽快知道小C

2018 FJUT ACM 校赛 j题 外传:魔王打工记(一)

外传:魔王打工记(一) TimeLimit:1000MS  MemoryLimit:128MB 64-bit integer IO format:%lld Problem Description 话说Home_W大魔王手下有四大天王: 首席战神--赛文斯,SoftWork首席科学家--布莱克,首席军师--金金金,首席狙击手--超无聊,首席苦力--小明. 然而,这些部下个个都是饭桶,把Home_W都快吃穷.虽然Home_W嘴上说:打工是不可能打工的,这辈子不可能打工的.烧杀抢又不会做,就只有当正义

HDU - 6513 Reverse It (SYSU校赛C题)(组合数学+容斥)

题目链接 题意:给定一个n*m的矩阵,可以选择至多两个子矩阵将其反转,求能形成多少种不同的矩阵. 任选一个矩阵有$C_{n+1}^{2}C_{m+1}^{2}$种方法,任选两个不同的矩阵有$C_{C_{n+1}^{2}C_{m+1}^{2}}^{2}$种方法,但其中有重复的,需要去重. 重复的情况一共有以下四种: 第一种,两矩阵拼合成一个矩阵,这样的图形有$C_{n+1}^{2}C_{m+1}^{2}$个,重复度(出现的次数)为(n+m-2) 第二种,形成的两个矩阵在同一行或同一列,有$C_{n

[水]浙大校赛补题

本来以为会巨难无比又有别的比赛可以打于是赛后补题,结果发现似乎略水,反正是找到了四个水题先贴下来 ZOJ-4099 J #include<iostream> #include<cstdio> #include<algorithm> using namespace std; typedef long long ll; int t; ll x, y, n; int main() { cin >> t; while (t--) { scanf("%lld