艰难取舍(Contest - ty2021cspJ专题练习之动规1)

2024-05-01 00:32

本文主要是介绍艰难取舍(Contest - ty2021cspJ专题练习之动规1),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

由于hyf长得实在是太帅了,英俊潇洒,风流倜傥,人见人爱,花见花开,车见车载。
有一群MM排队看hyf。每个MM都有自己独特的风格,由于hyf有着一颗包容的心,所以,什么风格的MM他都喜欢…… 
但是,hyf有一个特别的要求,他不希望总是看到风格得差不多的MM,更加特别的是,如果两个MM风格完全一样,hyf不会有任何意见。 
现在,hyf希望从去看他的MM中,去掉一些MM,从而使得相邻2个MM的风格值的差(绝对值)不为1。自然地,hyf希望去掉的MM越少越好。

输入

第一行一个整数N;

第2~N+1行N个整数,第i 个为ci。表示第i 个MM的风格值。

输出

一个数,表示最少要去掉的MM数。

样例输入Copy

6 
4 
2 
2 
1 
1 
1

样例输出Copy

2

提示

【数据范围】 
对于30%的数据,N≤20 
对于70%的数据,N≤100,ci ≤ 2000 
对于100%的数据,N≤1000  0 ≤ ci ≤ 2000 

代码:

#include<iostream>
#include<iomanip>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<cstdio>
#include<queue>
#include<list>
#include<vector>
#include<map>
using namespace std;
long long n,CC[1005],FF[1005],i;
int main(){
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>CC[i];
        FF[i]=1;
    }
    for(i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            if(abs(CC[i]-CC[j])!=1){
                FF[i]=max(FF[i],FF[j]+1);
            }    
        }
    }
    cout<<n-FF[n];
    return 0;
}

//                                                                                                                               ---lzp

这篇关于艰难取舍(Contest - ty2021cspJ专题练习之动规1)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/950303

相关文章

三国地理揭秘:为何北伐之路如此艰难,为何诸葛亮无法攻克陇右小城?

俗话说:天时不如地利,不是随便说说,诸葛亮六出祁山,连关中陇右的几座小城都攻不下来,行军山高路险,无法携带和建造攻城器械,是最难的,所以在汉中,无论从哪一方进攻,防守方都是一夫当关,万夫莫开;再加上千里运粮,根本不需要打,司马懿只需要坚守城池拼消耗就能不战而屈人之兵。 另一边,洛阳的虎牢关,一旦突破,洛阳就无险可守,这样的进军路线,才是顺势而为的用兵之道。 读历史的时候我们常常看到某一方势

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

RabbitMQ练习(AMQP 0-9-1 Overview)

1、What is AMQP 0-9-1 AMQP 0-9-1(高级消息队列协议)是一种网络协议,它允许遵从该协议的客户端(Publisher或者Consumer)应用程序与遵从该协议的消息中间件代理(Broker,如RabbitMQ)进行通信。 AMQP 0-9-1模型的核心概念包括消息发布者(producers/publisher)、消息(messages)、交换机(exchanges)、

音视频入门基础:WAV专题(10)——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础:WAV专题(6)——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道,通过FFprobe命令可以打印WAV音频文件每个packet(也称为数据包或多媒体包)的信息,这些信息包含该packet的pts、dts: 打印出来的“pts”实际是AVPacket结构体中的成员变量pts,是以AVStream->time_base为单位的显

【Rust练习】12.枚举

练习题来自:https://practice-zh.course.rs/compound-types/enum.html 1 // 修复错误enum Number {Zero,One,Two,}enum Number1 {Zero = 0,One,Two,}// C语言风格的枚举定义enum Number2 {Zero = 0.0,One = 1.0,Two = 2.0,}fn m

MySql 事务练习

事务(transaction) -- 事务 transaction-- 事务是一组操作的集合,是一个不可分割的工作单位,事务会将所有的操作作为一个整体一起向系统提交或撤销请求-- 事务的操作要么同时成功,要么同时失败-- MySql的事务默认是自动提交的,当执行一个DML语句,MySql会立即自动隐式提交事务-- 常见案例:银行转账-- 逻辑:A给B转账1000:1.查询

html css jquery选项卡 代码练习小项目

在学习 html 和 css jquery 结合使用的时候 做好是能尝试做一些简单的小功能,来提高自己的 逻辑能力,熟悉代码的编写语法 下面分享一段代码 使用html css jquery选项卡 代码练习 <div class="box"><dl class="tab"><dd class="active">手机</dd><dd>家电</dd><dd>服装</dd><dd>数码</dd><dd