专注于互联网--专注于架构

usaco:usaco 4.3 Buy Low, Buy Lower 动态规划

典型的动态规划，难点是第二步，cnt[i]表示以a[i]结尾的最长下降序列的种数，则 cnt[i] = count( len[k]+1==len[i]), 1<=k < i ， 其中len[i]表示以a[i]结尾的最长下降子序列长度 还有一个问题，如果生成的实际序列值相等，则算作一种，可以通过一下方法处理： 计算出a[i]之后和第一个和a[i]相等的数a[k]，令next[i] = k; 如果没有相等的则next[i] = 0 计数时如果 next[j]!=0 && next[j] < i ，则不累计，因为位于j和i之间的 [阅读全文] [PDF]