2022/1/14总结

T1:3499. 【NOIP2013模拟联考15】人类基因组(genes)

将基因断环成列，维护rmq（单调队列，st表，笛卡尔树，线段树……）

T2:1339. 矿泉水 _{(Standard IO)}

这题写起来有点复杂，先把（n+1 ~ 4）的水转化成废水即喜好值为9，价格为0，我们设f[i,j,k,l,u]表示第i天，j天内要喝第1种水，k天内要喝第2种水，l天内要喝第3种水，u天内要喝第4种水

上伪代码：

 for(i=0~m-1,j=1~a[1],k=1~a[2],l=1~a[3],u=1~a[4])
{
    不喝水 : f[i][j][k][l][u]->f[i+1][j-1][k-1][l-1][u-1]
    喝水 : f[i][j][k][l][u]->f[i][...a[?]...]
    记录答案 : if can : day=i，money=max{f[i][j][k][l][u]}
}

T3：1341. 失眠 _{(Standard IO)}
设S1=（i，j，k）的个数（a[i]<a[j] and a[k]<a[j])
设S2=（i，j，k）的个数（a[i]<a[j] and a[j]<a[k])
设S3=（i，j，k）的个数（a[i]<a[j] and a[j]<a[k])

S2,S3很好求，所以求出S2，S3，得到S1=S3-S2

QBFNB！用cdq分治A了此题

T4：3739. 匹配(match)

跑出一个最二分图最大权匹配，逐一验证每条边即可