USACO 低价购买 Buy Low

这貌似是一道求最长下降序列的线性DP。

首先最长下降序列的状态转移方程是最简单的了QAQ

 

 

当然了f[i]默认值是1;

或者可以这样

 

接下来是统计方案 如果不计重的话貌似很好办,但要是计重的话,就应该倒推,如果前面的元素k和目前的元素i相等,那么f[k]==f[i],{这是因为统计了最长下降序列(如果是不上升序列的话还要稍微改动一下i对答案的贡献)}

所以k对答案的贡献应是和i相等的,这时可以把i对答案的贡献去掉了,因为以i结尾的组合把i换为k都成立这是由于由k结尾的最长下降序列的方案数只取决于k前面的几个元素(不同元素的组合)而与k无关

 

从而得出整个状态转移方程:

注意这里n初始化为1,组合数必定大于等于1

所以,完成了全部程序:

 

 

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据