首页 > 其他分享 >【题解】Solution Set - NOIP2024集训Day36 dp 优化 + 状态设计

【题解】Solution Set - NOIP2024集训Day36 dp 优化 + 状态设计

时间:2024-09-23 16:35:07浏览次数:8  
标签:Set Day36 题解 Solution dp NOIP2024

【题解】Solution Set - NOIP2024集训Day36 dp 优化 + 状态设计

https://www.becoder.com.cn/contest/5550

最后一题较难。


「NOIP2023」天天爱打卡

考虑 dp。

\(f_{i,j}\):前 \(i\) 天,到第 \(i\) 天为止连续打卡 \(j\) 天。

有转移:

\[f_{i,0}=\max(f_{i,j})\\ f_{i,j}=\max(f_{i-1,j-1}-d+w(i,j))\\ w(i,j)=\sum_{k=1}^m[x_k=i\wedge j\ge y_k]v_k \]

2min finished bf. Let me try try. (


bf \(O(nkm)\)

好的,这显然是对的,现在考虑优化。

首先可以对 \(x\) 离散化。

标签:Set,Day36,题解,Solution,dp,NOIP2024
From: https://www.cnblogs.com/CloudWings/p/18427282

相关文章

  • Codeforces Round 972(Div.2)题解
    CodeforcesRound972(Div.2)题解A.SimplePalindrome贪心贪心,尽可能元素数量平均,并且相同字母放在一起。#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#definepbpush_back#defineall(u)u.begin(),u.end()#defineendl'\n'#de......
  • Codeforces Round 973 (Div.2) A-E题解
    CodeforcesRound973(Div.2)A-E题解比赛传送门A.Zhan'sBlender数学显然答案为\(\lceil\frac{n}{min(x,y)}\rceil\)。#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#definepbpush_back#defineall(u)u.begin(),u.en......
  • 题解:AT_abc372_e [ABC372E] K-th Largest Connected Components
    题意给出\(q\)个操作。将\(u\)和\(v\)连边。问\(u\)所在的连通块中编号第\(k\)大的点。思路连通块很容易想到并查集,求第\(k\)大可以用平衡树(虽然赛时没看到\(k\le10\)),合并时将信息从将小的连通块合并到大的连通块,这样可以减少时间复杂度。什么?你不会写平衡......
  • 题解:AT_arc184_a [ARC184A] Appraiser
    题意\(1000\)个硬币中有\(10\)个假币,你每次可以询问两个位置的硬币类型是否相同,你需要用不超过\(950\)次询问找出所有假币的位置。思路将前\(990\)个硬币每\(11\)个分一组,共\(90\)组,余\(10\)个单独分一组。询问每组第\(1\)个硬币和这组后面硬币的关系。因为只......
  • 使用Redis的SETNX命令实现分布式锁
    什么是分布式锁分布式锁是一种用于在分布式系统中控制多个节点对共享资源进行访问的机制。在分布式系统中,由于多个节点可能同时访问和修改同一个资源,因此需要一种方法来确保在任意时刻只有一个节点能够对资源进行操作,以避免数据不一致或冲突。分布式锁就是用来实现这种互斥访问的......
  • CF1270H Number of Components 题解
    Description给一个长度为\(n\)的数组\(a\),\(a\)中的元素两两不同。对于每个数对\((i,j)(i<j)\),若\(a_i<a_j\),则让\(i\)向\(j\)连一条边。求图中连通块个数。支持\(q\)次修改数组某个位置的值,每次修改后输出图中连通块个数。\(n,q\le5\times10^5,1\lea_i\le10^......
  • 2024ICPC网络赛第二场题解(部分)
    前言这场相对作用大一点,最后顶着队友的怀疑压力乱搞出了C,但是后面看题解发现似乎是数据弱了跑过去,其实复杂度是队友分析的那样,是不正确的,但是毕竟是打名额的比赛,过了就是过了,这里分享一下C题的乱搞做法,以及其他题的我们队赛时代码。下面的顺序按过题顺序(也差不多是难度递增顺序)......
  • 网站程序打不开数据库错误等常见问题解决方法
    当遇到网站打不开或者数据库错误等问题时,可以按照以下步骤来诊断并解决问题:检查网站根目录:如果上传数据后显示“主机开设成功!”或“恭喜,lanmp安装成功!”,这通常是因为服务器默认放置了一个index.htm文件。此时应检查wwwroot目录内是否有自己的程序文件,并考虑删除默认的index.h......
  • 题解:AT_arc184_a [ARC184A] Appraiser
    本质上还是官方题解的分组并利用\(M\)不大的思路。询问次数\(Q\)离最简单的每个扫一遍就可以知道答案的做法少了\(50\)次。我们考虑如何减少这个次数。首先你可以发现一次询问可以覆盖到两个数,也就是说所有的数都被覆盖时只需要询问\(500\)次。我们考虑把不同的对拉出......
  • 网站打不开数据库错误等常见问题解决方法
    当遇到网站打不开且出现数据库错误等问题时,可以采取以下步骤进行排查和解决:检查默认页面:如果网站显示“主机开设成功!”或者“恭喜,lanmp安装成功!”这样的信息,这可能是服务器默认放置的页面。检查wwwroot目录下是否有自己的程序文件,如果没有,上传正确的文件,并删除默认的index.ht......