首页 > 其他分享 >NOIP2023 T4 题解

NOIP2023 T4 题解

时间:2024-03-02 16:55:42浏览次数:39  
标签:max prize 题解 T4 rev times st NOIP2023 now

T4

写出转移方程:\(f_i\) 表示前 \(i\) 天且第 \(i\) 天必须跑的最大能量值。\(g_i=\max\limits_{j=1}^i\{f_j\}\)。初值 \(f_0=g_0=0\)。

对于转移方程,考虑枚举最后一段跑的段是从哪里开始的:\(f_i=\displaystyle\max_{j=i-k+1}^i(g_{j-2}+prize(j,i)-(j-i+1)\times d)\)。其中 \(prize(j,i)\) 是 \([j,i]\) 跑获得的奖励。

注意如果 \(j=1\) 要特判。

这个转移方程是 \(O(n^2m)\) 的。我们发现,每一个跑段的起终点一定是某个挑战的起终点,所以我们可以离散化。

(注意离散化后还要数组对应到原来坐标,注意离散化后的转移可能有两种:① 上一个离散点就在前一个 ② 上一个点不相邻

然后我们发现这玩意可以用线段树优化:线段树第 \(i\) 个结点,表示当前的决策点为 \(i\) 时的值。

具体而言:

for (ll i = 1, p = 1; i <= cur; i++) { 
	while (p < i && rev[i] - rev[p] + 1 > k) //p指向当前第一个在rev[i]-k+1之后的 
		p++;
	for (auto ch: chl[i])
		st.mdf(1, 1, st.sz + 1, 1, ch.l + 1, ch.v);
	ll tmp = (rev[i - 1] == rev[i] - 1 ? max(0ll, i - 2) : i - 1); //找到上一个决策点 
	st.mdf(1, 1, st.sz + 1, i, i + 1, g[tmp] + (rev[i] - 1) * d);
	
	f[i] = st.qry(1, 1, st.sz + 1, p, i + 1) - rev[i] * d;
	g[i] = max(g[i - 1], f[i]);
}

\(rev_i\) 是离散化后的原坐标。

当 \(now\) 右移一个,首先要枚举所有右端点是 \(now\) 的挑战,然后对 \([lft,now]\) 进行区间加 \(prize\)。

对位置 \(now\) 的决策设初值:\(g[now-1/now-2]+(rev[now]-1)\times d\)。

\(f[i]=st.qry(p,i+1)-rev[i]\times d\)。

为什么?我们把 \(f\) 的转移方程做变形:\(f_i=\max(g[j-1]+prize(j,i)-(i-j+1)\times d)\),其中 \(prize(j,i)\) 的累加用了线段树,而 \(-(i-j+1)\times d=(j-1)\times d-i\times d\)。

所以我们在每个决策位置 \(j\) 都预先 \(+(j-1)\times d\),算 \(f_i\) 的时候只需要求 \(\max\) 再减去就行了。

(有点像斜率优化:拆式子,费用提前计算)

还有,数据卡常。不能 map 离散化,要用 sort

标签:max,prize,题解,T4,rev,times,st,NOIP2023,now
From: https://www.cnblogs.com/FLY-lai/p/18048845

相关文章

  • SP14846 GCJ1C09C - Bribe the Prisoners 题解
    非常好区间dp。我们发现直接依题做是困难的,因此考虑反着做。也即,假定起初那\(Q\)个牢房均为空,现在要将给定的\(Q\)的犯人插入其中,求最小代价。然后我们发现这题和P1775很像,相当于每插入一个人,两段不相邻的牢房就被合并到了一起。接着我们就考虑这玩意怎么做区间dp。......
  • 【题解】「HDU 7084」Pty loves string
    CQBZOJHDU7084不难想到把最终在\(S\)从中间分开,就变成了前后两个broder拼起来。考场重现:直接把所有的broder求出来,将相同长度的broder的下标存在一起,然后暴力匹配,最后还没来及优化。考场代码(除了fail树,其她其实都挺逼近正解正解是建出fail树(甚至搞忘还有这东......
  • 2023互联网笔试记录汇总(61道真题+题解)
    以下编程题均为博主在2023年投递实习和秋招过程中的笔试真题(共61道编程题),为避免不必要的麻烦,不对题目的来源进行说明。3.4第一题题意:给一个数组(n≤2e5),求数组内任意数对的最大差值。即对任意i<j,求最大的x[j]-x[i]。题解:处理一下前缀最小值。第二题题意:给一个数组(n≤2e5......
  • 信息传递(题解)[并查集]
    题目题目描述有n个同学(编号为1到n)正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为i的同学的信息传递对象是编号为Ti同学。游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有......
  • P10187 [USACO24FEB] Palindrome Game B 题解
    挑战题解区最短代码回文数?数学题!打表找规律吧……显然,\(1\sim9\)都是回文数,先手赢(就一位你还想咋地啊)。然后是\(10\)。样例告诉我们,这个不行。接着是\(11\sim19\),发现随便减个\(1\sim9\)就可以变成\(10\),而\(10\)是后手赢。赢得就是后手的后手,那就是先手,可以。......
  • P10189 [USACO24FEB] Maximizing Productivity B 题解
    先说说暴力做法:每次遍历一遍,看看是否满足\(t_i+s\lec_i\),满足就计数,不满足就挂。单次时间复杂度显然为\(O(N)\),总得时间复杂度约为\(O(NQ)\),TLE是肯定的~暴力代码//Problem:Problem3.MaximizingProductivity//Contest:USACO-USACO2024FebruaryContest,......
  • ABC295D 题解
    萌萌思维题,但是考场差一点AC。题目等价于寻找区间\([l,r]\)满足数字\(0\)~\(9\)各出现偶数次。根据找筷子这道题的经验,出现偶数次=异或和为\(0\)。但是发现如果和找筷子一样直接异或到一起会出现冲突(例子:$3\oplus5\oplus6=0$)。所以变成二进制数就可以了。......
  • ABC321F 题解
    可撤销背包的模板题。如果没有减操作就是\(01\)背包,众所周知转移方程是\(f[i]=f[i]+f[i-v]\)。考虑减操作,对于一个重量\(i\),不选物品\(v\)的方案数是什么呢?发现我们只需要把选\(v\)的方案去掉就好,那么转移方程就是\(f[i]=f[i]-f[i-v]\)。于是就做完了。注意取模变正......
  • ABC323D 题解
    这个题笔者场上Wa了六次……首先发现一个性质:考虑单个的\(s\),它自己所能合并成的块就是\(c\)的二进制表示。例如当\(s=3,c=7\)时,显然我们可以先两两合并,得到\(3\)个\(s=6\)的,再把其中的两个合并得到一个\(s=12\)的。发现\(7=(111)_2\),正好最终只有三个块:\(s=3,......
  • P3749 题解
    P3749[六省联考2017]寿司餐厅题解发现很少有人讲为什么这题是最大权闭合子图,但作为一个刚学网络流的蒟蒻,我认为考虑是必要的。最大权闭合子图的特点:存在单向依赖关系,选\(x\)必须选\(y\)。每个点只会被选一次。代价有正有负。本问题特点:选一个区间,必选所有子区间(......