noip模拟47

本文主要是介绍noip模拟47，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

原版在 \(linux\) 本地写完没保存关机给没了……
再简单写一下

\(t2\) 用 \(dp\) 转移 \(f[i]=\sum _ {j=last[a[i]]}^{i-1} f[j]\)
用前缀和优化为 \(sum[i]=sum[i-1]*2-sum[i-k-1]\)
贪心选取最后出现位置最靠左的，矩乘优化转移

\(t3\) \(f[i]=(f[i-1]+1)*p[i]+f[i-1]*t * p[i]\)
注意答案是 \(\sum f[i-1] * p[i]\)
因为这一位如果为零没贡献
然后线段树维护转移，整个区间每一项写成 \(f[r]=kf[l-1]+b\)，最终答案也是 \(sumkf[l-1]+sumb\)，用线段树动态维护这四个量即可

这篇关于noip模拟47的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！