USACO/buylow

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是USACO Chapter 4 .3中的OI题目Buy Low,Buy Lower的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。

问题分析

动态规划题，就是最长下降序列问题。第一问可以用O(N^2)的算法解决。

s[i]为序列中第i项的值，MaxLength[i]为以第i项为末尾中最长下降序列长度。

状态转移方程为 MaxLength[i]=max{MaxLength[j]}+1 (j=1..i-1 and s[j]>s[i])

初始条件

MaxLength[1]=1

对于第二问求最长下降序列的数量，可以通过求第一问的过程解决。设MaxCnt[i]为第i项为末尾中最长下降序列的个数。

对于所有的j(1≤j≤i-1)如果有(s[j]>s[i] 并且 MaxLength[j]+1>MaxLength[i])则MaxCnt[i]=MaxCnt[j]，否则如果(MaxLength[j]+1= =MaxLength[i])可利用加法原理，MaxCnt[i]=MaxCnt[i]+MaxCnt[j]。

考虑到题目中说的不能又重复的序列，我们可以增加一个域Next[i]表示大于i且离i最近的Next[i]使得第Next[i]个数与第i个数相同。如果不存在这样的数则Next[i]=0。这样我们在DP的时候如果出现Next[j]不为0且Next[j]<i可直接跳过。

这个题数据规模很大，用高精.

优化技巧

1. 可以在给出的序列的末尾增加一个0，这样直接统计以最后一个0结尾的最长下降子序列即可。
2. 显然题目的规模要求我们用高精度。可以使用longint，8位8位的加以节省时间。

判重方法2

对于任意一个 f[i]=max(f[j])+1; 1<=j<i; 设g[i] 为到计算 i 的方案总数 若完成后f[i]值为ans[i] 若不判重 那么 g[i]=sum(g[j]){ f[j]=ans[i];1<=j<i} 那么容易知道对于所有具有相同 f[j] 的原数列值必为不降，如果有一降序，则必定会导致以该位置结尾的最长下降子序列长度增加，所以可以记录上一位置的a[j]数值，相同a[j]的g[j]无需加入即可。 (及去掉这个不升序列中的相等部分 注意 去掉靠前的)

for i:=2 to n do
    for j:=i-1 downto 1 do//注意此处从i-1开始循环

---

3.现在还有一个问题。就是遇到 前驱位 两个相同的数，是随便取一位么？有讲究么？

当然！例如：

原始9 7 5 8 5 1 Dp 1 2 3 2 3 4 Num 1 1 1 1 2 2

想必大家已经注意到了：对于第一个出现的5和第二个5，他们的dp一样，但是num却不一样。这里我们可以取最后一个5，原因如下： 对于非最后一个5的序列，最后一个5，一定可以取得。例如对于第二个5，第一个5的9 7 5序列，第二个5同样可以取得。而且后面的5可能会有更多的取法，例如上例中的第二个5，还可以获得9 8 5这个序列。所以我们这里，最后1对应的num应该是2

判重方法3

记录ago[i]为1到i-1中位置与i最接近且股价相同的位置（没有就记录为0),显然ago[i]的状态是由之前的状态推出来的，所以i的状态如果也由ago[i]之前的状态推出来的，那么定然重复，所以i的状态一定是由ago[i]+1 to i-1所推出来的，此时因为ago[i]+1 to i-1已经处理过，其中也无重复，所以此时i的状态一定没有重复。（因为最初是一定有不重复的，所以由这些不重复的状态推出来的也一定不会重复）。具体程序见Pascal程序代码

局部哈希+记忆化搜索

http://www.oibh.org/bbs/thread-35824-1-1.html

范例程序

• Pascal程序代码
• C++程序代码

参考

CmYkRgB123
Barty