upc 艰难取舍 最长上升子序列
发布日期:2021-09-25 23:57:37 浏览次数:1 分类:技术文章

本文共 1207 字,大约阅读时间需要 4 分钟。

艰难取舍
时间限制: 1 Sec 内存限制: 128 MB

题目描述
由于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

题意让你找到最少去掉的MM个数,我们可以转换成求最长的满足条件的序列,让后用 n - max 即可,直接套个最长上升子序列模板,让后把转移的条件改成 abs ( a[ i ] - a[ j ] ) != 1即可。
注意设置初始长度以及设置的位置,一开始放第二个for里面一直wa.

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y secondusing namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=3010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n;int a[N],f[N];int main(){    //
                
ios::sync_with_stdio(false);//
cin.tie(0);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),f[i]=1;
int ans=-1;
for(int i=1;i<=n;i++)
for(int j=1;j
{    
if(abs(a[i]-a[j])!=1)
f[i]=max(f[i],f[j]+1);
}
for(int i=1;i<=n;i++)
ans=max(ans,f[i]);
printf("%d\n",n-ans);
return 0;}

转载地址:https://blog.csdn.net/DaNIelLAk/article/details/105823397 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:upc 奇怪的道路 分形之城---改版
下一篇:upc 工作团队 并查集 + 虚父节点

发表评论

最新留言

很好
[***.11.159.49]2022年05月30日 15时16分14秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章

加班越久故障越多,如何跳出程序员的恶性循环? 2021-10-11
这是阿里人的双11记忆 2021-10-11
实力亲测 | 如何用云盾WAF做漏洞急救 2021-10-11
当一个程序员写不出代码了,该怎么办? 2021-10-11
2017杭州云栖大会参会体验 2021-10-11
在 WPA2 安全协议存在漏洞的情况下,我们应该如何保护自己? 2021-10-11
程序员,这个双十一,对自己好一点… 2021-10-11
做人、做事,做架构师——架构师能力模型解析 2021-10-11
马云:阿里巴巴必须成为国家和世界创新的发动机 2021-10-11
10月26日云栖精选夜读:如何让数据价值最大化?阿里全域大数据系统深度解读 2021-10-11
WordPress4.8.1版本存在XSS跨站攻击漏洞 2021-10-11
应对双11挑战,阿里巴巴智能化运维体系演进与建设 2021-10-11
无人化运维离我们有多远?阿里智能化运帷平台深度揭秘 2021-10-11
曾鸣:为什么要让「听得见炮火的士兵」做决定?| 干货 2021-10-11
【安全预警公告】新勒索病毒Bad Rabbit(坏兔子)来袭,请做好防御准备 2021-10-11
阿里云双11活动撸福利攻略云服务器篇 必买爆款,包年低至240元 2021-10-11
独家 | 一文读懂集成学习(附学习资源) 2021-10-11
MaxCompute 2.0 NewSQL演进之路 2021-10-11
MaxCompute2.0 对开源系统的支持与融合 2021-10-11
10月25日云栖精选夜读:全世界都在关注中国企业的互联网架构?云栖大会道出了真相 2021-10-11