首页 > 其他分享 >AtCoder Regular Contest 120 F Wine Thief

AtCoder Regular Contest 120 F Wine Thief

时间:2023-04-26 20:37:11浏览次数:48  
标签:AtCoder Contest 传送门 Thief len times 答案

洛谷传送门

AtCoder 传送门

Hint 如果是一个环怎么做?
Answer 由于是一个环,因此环上每个点对最终答案造成的贡献都相同。设 $f_{i,j}$ 为长度为 $i$ 的序列选 $j$ 个不相邻的点的方案数,则 $f_{i,j} = \binom{i-j+1}{j}$。应该很好理解,考虑一个长度为 $i-j+1$ 的链,链头、链尾和两个数之间都可以插入一个元素,总共需要插入 $j$ 个,因此方案数是 $\binom{i-j+1}{j}$。每个点对答案的贡献为 $a_i \times f_{n-3,k-1}$(就是钦定这个点不选,断环为链)。

这启发我们在环的基础上考虑。发现除了环的答案,链的要多考虑两端都选的方案。设 \(g_{i,j,k}\) 为在 \([i,j]\) 的链选 \(k\) 个不相邻的点的答案。令 \(len = j - i + 1\),那么:

\[g_{i,j,k} = f_{len-3,k-1} \times (\sum\limits_{p=i}^j a_p) + f_{len-4,k-2} \times (a_i + a_j) + g_{i+2,j-2,k-2} \]

第一部分是环的答案,后面是钦定选 \(a_i,a_j\),\([i+2,j-2]\) 选点的方案为 \(f_{len-4,k-2}\),作为系数乘上 \(a_i + a_j\),最后再递归下去。

时间复杂度 \(O(n)\)。

标签:AtCoder,Contest,传送门,Thief,len,times,答案
From: https://www.cnblogs.com/zltzlt-blog/p/17357174.html

相关文章

  • AtCoder Regular Contest 125 E Snack
    洛谷传送门AtCoder传送门很棒的flow题,考虑建二分图。源点向每种零食连边权为\(a_i\)的边,每种零食向每个孩子连边权为\(b_j\)的边,每个孩子向汇点连边权为\(c_j\)的边,这个图的最大流就是答案。直接跑最大流肯定T,考虑最大流等价于求这个图的最小割,因此转而求最小割。......
  • AtCoder Regular Contest 126 D Pure Straight
    洛谷传送门AtCoder传送门很不错的状压。考虑先把最后作为答案的数聚到一起,再算它们的逆序对个数。设\(f_S\)为当前选的数集合为\(S\)的答案。有转移:选\(a_i\),答案加上之前选的比它大的数;不选\(a_i\),此时需要把左边的数或者右边的数往中间挪一个,答案加上左右两端的最......
  • SMU Spring 2023 Trial Contest Round 10
    SMUSpring2023TrialContestRound10 A-RemoveDuplicates#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;typedefpair<string,int>PSI;constintN=2e2+5,INF=0x3f3f3f3f,Mod=1e6;constdoubleeps=1e-6;typedef......
  • AtCoder Regular Contest 115 F Migration
    洛谷传送门AtCoder传送门这种最大值最小化的题一般可以先考虑二分。设二分了一个\(mid\)。记\(A=(a_1,a_2,...,a_k)\)为表示每个棋子的位置的状态,如果\(A,B\)可以互相到达,就在它们之间连一条无向边。则要判断的是\(S=(s_1,s_2,...,s_k)\)和\(T=(t_1,t_2,...,t_k......
  • 2017 ACM-ICPC, Universidad Nacional de Colombia Programming Contest D
    AlexhastwomagicmachinesAandB.MachineAwillgiveyou2x + 1coinsifyouinsertxcoinsinit,machineBwillgiveyou2x + 2.Alexhasnocoinsandwantstogetexactlyncoinsinordertobuyanewunicorn,buthecan’tfigureouthowtodoi......
  • 2014 Pacific Northwest Region Programming Contest—Division 2 Problem U — lim
    Incollegefootball,manydifferentsourcescreatealistoftheTop25teamsinthecountry.Sinceit’ssubjective,theselistsoftendiffer,butthey’reusuallyverysimilar.Yourjobistocomparetwooftheselists,anddeterminewheretheyaresimi......
  • XI Samara Regional Intercollegiate Programming Contest Problem J. Parallelogram
    Therearensticks,thei-thofwhichhaslengthai.Alexwantstoassemblefromthemasmanyparallelogramsaspossiblesimultaneously,witheachstickusedatmostinoneparallelogram.Whatmaximalnumberofparallelogramsisitpossibletoassembl......
  • XI Samara Regional Intercollegiate Programming Contest Problem E. Substring Re
    Twostringssandtofthesamelengtharegiven.Determinewhetheritispossibletomaketfromsusingexactlyonereverseofsomeitssubstring.InputThefirstlinecontainsthestrings,andthesecond—thestringt.Bothstringshavethesamel......
  • XI Samara Regional Intercollegiate Programming Contest Problem L. Queries on a
    Astringsisgiven.Alsothereisastringp,andinitiallyitisempty.Youneedtoperformqoperationsofkind«addalettertotheendofthestringp»and«removealetterfromtheendofthestringp»,andafterperformingeachoperationyoumu......
  • XI Samara Regional Intercollegiate Programming Contest Problem K. Video Reviews
    Thestudio«LodkaGaming»isengagedinadvertisingoftheirnewgame«.C.O.N.T.E.S.T:UnexpectedBehaviour».Thestudio’smarketerisplanningtocommunicatewithnvideobloggersonebyone(inthepredeterminedorder,startingfromthe1-standend......