首页 > 其他分享 >F. Feed Cats

F. Feed Cats

时间:2024-07-07 09:42:23浏览次数:15  
标签:Feed pre int farl -- Cats 端点 dp

原题链接

题解

每个点要么喂,要么不喂,我们令 \(dp[i]\) 为前 \(i\) 个步骤最多能喂养多少猫,易得 \(dp[i]\) 是单调不减的
我们再维护每个点被包含的区间里的最左端 \(l\)
这样一来 \(dp[i]=max(dp[i-1],dp[l-1]+sum)\)

可是如何维护每个点被包含区间的最左端呢?
我们先记录下每个右端点的最小左端点,然后逆序遍历,即对于 \(i\) 求以 \([i,n]\) 内为右端点的最小左端点

code

#include<bits/stdc++.h>
using namespace std;

int farl[2000005],pre[1000006]={0},dp[1000006];
int main()
{
    int t;
    cin>>t;

    while(t--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            farl[i]=n+1;
            pre[i]=0;
        }

        for(int i=1;i<=m;i++)
        {
            int x,y;
            cin>>x>>y;
            pre[x]++;
            pre[y+1]--;

            farl[y]=min(farl[y],x);
        }

        for(int i=n-1;i>=1;i--) farl[i]=min(farl[i],farl[i+1]);

        int sum=0,ans=0;
        for(int i=1;i<=n;i++)
        {
            sum+=pre[i];

            dp[i]=dp[i-1];
            if(farl[i]<=i) dp[i]=max(dp[i],dp[farl[i]-1]+sum);
            ans=max(ans,dp[i]);
        }
        cout<<ans<<'\n';
    }
    return 0;
}

标签:Feed,pre,int,farl,--,Cats,端点,dp
From: https://www.cnblogs.com/pure4knowledge/p/18288219

相关文章

  • 关注推送---Feed流,推模式实现的个人分析及其思考。
    本篇文章记录我们实际开发过程中,关注推送场景的个人思考,以及解析。文章目录前言一、关注推送是什么?是什么是Feed流?二、解决关注推送问题的技术方案1.理论模型的选取2.数据类型的选取三、理论模型的选取三、数据类型的选取总结前言⁣⁣⁣⁣⁣⁣⁣⁣本篇文章......
  • [题解]CF311B Cats Transport
    思路首先,对于每一只小猫刚好玩完就被饲养员接走的出发时间必定为\(t_i-sd_i\)。那么,我们令\(a_i=t_i-sd_i\)表示第\(i\)只小猫的最早出发时间。因此,对于第\(k\)时刻出发的饲养员能接到的小猫当且仅当满足\(a_i\leqk\)。然后,我们定义\(dp_{i,j}\)表示用\(i\)......
  • 【YOLOv8改进】MSFN(Multi-Scale Feed-Forward Network):多尺度前馈网络
    摘要摘要——高光谱图像(HSI)去噪对于高光谱数据的有效分析和解释至关重要。然而,同时建模全局和局部特征以增强HSI去噪的研究却很少。在本文中,我们提出了一种混合卷积和注意力网络(HCANet),该网络结合了卷积神经网络(CNN)和Transformers的优势。为了增强全局和局部特征的建模,我们设计了......
  • 美食社交--feed服务
    前言:本篇博客Feed服务是美食社交项目内第六篇文章,是写在好友服务之后的一篇博客,大家可以先尝试阅读并编写第五篇–美食社交好友服务的文章之后再阅读此文,效果更佳;因为两者是有联系的!1.概念移动互联网时代,Feed流产品非常常见,比如朋友圈,微博,非常典型的Feed流产品,还有图......
  • 23 feed
      feed=supply,thewateroriginatesfromthrash=novefromsidetosideinaviolentwayflingmyarmsandlegsfastandenergeticallyoutput=thepower,energy,etc.producea 这段文字中的几个关键词描述了游泳的动作和相关的一些概念:1.**feed**-这个词在原......
  • Transformer模型-Feed Forward前馈网络和Relu激活函数的简明介绍
     今天介绍transformer模型的FeedForwardnetwork前馈网络和Relu激活函数背景位置感知Position-Wise前馈网络(FFN)由两个全连接层(fullyconnecteddenselayers,就是线性层(LinearLayer),或密集层(DenseLayer))组成,或者也可以称为多层感知机(MLP:multi-layerperceptron)。 参见:Tr......
  • const [increaseBigCats, increaseSmallCats] = useCatStore( (state) => [state.incr
    const[increaseBigCats,increaseSmallCats]=useCatStore((state)=>[state.increaseBigCats,state.increaseSmallCats],shallow);这段代码是在使用zustand这个React状态管理库。zustand提供了一种简洁的方式来创建可复用的状态存储,并允许组件通过hoo......
  • 【Coursera GenAI with LLM】 Week 3 Reinforcement Learning from Human Feedback Cl
    Helpful?Honest?Harmless?MakesureAIresponseinthose3ways.Ifnot,weneedRLHFisreducethetoxicityoftheLLM.Reinforcementlearning:isatypeofmachinelearninginwhichanagentlearnstomakedecisionsrelatedtoaspecificgoalbytakin......
  • Denoising Implicit Feedback for Recommendation论文阅读笔记
    Abstract​ 隐式反馈的普遍性使它们成为构建在线推荐系统的默认选择。虽然大量的隐式反馈缓解了数据的稀疏性问题,但缺点是它们在反映用户的实际满意度方面没有那么干净。例如,在电子商务中,很大一部分点击并不能转化为购买,许多购买最终会得到负面评论。因此,解释隐式反馈中不可避免......
  • 知识点try catsh
     /*trycatch:自己处理异常*try{*可能出现异常的代码*}catch(异常类名Ae){*如果出现了异常类A类型的异常,那么执行该代码*}...(catch可以有多个)*finally{*最终肯定必须要执行的代码(例如释放资源的代码)*}*代码执行的顺序:*1.try内的代码从出现异常的那......