USACO Buy low, buy lower

这道题是动态规划的经典题目。
要得到最长下降序列长度是很容易的，用max[i]表示以第i个数字结尾的最长下降序列的长度，可以得到一下几个结论
1）max[i]只与前i个数字有关
2）max[i]满足最优子结构性质
因此，用下面的过程就可以获得所有max[i]

C语言: 高亮代码由发芽网提供

1 for(i = 0;i < N;i ++)
2 {
3     max[i] = 1;
4     for(j = 0;j < i;j ++)
5         if(price[j] > price[i] && max[j] + 1 > max[i])
6             max[i] = max[j] + 1;
7 }

至此，问题已经解决一半了，接下来就是如何计数，大部分读者应该都想到了这个方法，在计算max[i]的过程中统计cnt[i]

C语言: 高亮代码由发芽网提供

01 for(i = 0;i < N;i ++)
02     for(j = 0;j < i;j ++)
03         if(price[j] > price[i])
04         {
05             if(max[j] + 1 > max[i])
06             {
07                 max[i] = max[j] + 1;
08                 cnt[i] = cnt[j]
09             }
10             else if(max[j] + 1 == max[i])
11             {
12                 cnt[i] += cnt[j];
13             }
14         }

可是，上面的代码不能完全符合要求。题目中有这么一句：In counting the number of solutions, two potential solutions are considered the same (and would only count as one solution) if they repeat the same string of decreasing prices, that is, if they "look the same" when the successive prices are compared.
而上面代码的缺陷就是——会重复计数。

如何避免这个问题呢？

先让我们想一下这个问题是如何发生的，就拿3 2 2 1为例：

idx     0    1    2    3
price  3    2    2    1
max   1    2    2    3
cnt     1    1    1    2

可以看到，在计算cnt[3]的时候，前面的2被计算了两次。并且读者可以发现，这种累加的错误也满足“子结构性质”。只要避免这个问题，就可以得到正确的结果。

避免累加相同数字的方法有很多。在本人的程序中，使用一个附加数组next，先用N^2的时间算出next数组，然后在计算cnt的时候略加判断即可。

此外，这个题目还有个很坑人的地方——要使用高精度。

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #define MAX_LENGTH 100
05
06 typedef struct bignum
07 {
08     int len;
09     char digit[MAX_LENGTH];
10 }bignum;
11
12 long price[5010];
13 int max[5010];
14 bignum cnt[5010];
15 int next[5010] = {};
16 int N;
17
18 int getmax(int a,int b)
19 {
20     if(a > b)    return a;
21     return b;
22 }
23
24 bignum plus(bignum a,bignum b)
25 {
26     bignum c;
27     memset(&c,0,sizeof(bignum));    //don't forget this
28     c.len = getmax(a.len,b.len);
29     int i;
30     int carry = 0;
31     for(i = 0;i < c.len;i ++)
32     {
33         carry += a.digit[i] + b.digit[i];
34         c.digit[i] = carry % 10;
35         carry /= 10;
36     }
37     if(carry > 0)
38     {
39         c.digit[c.len] = carry;
40         c.len ++;
41     }
42     return c;
43 }
44
45 int main()
46 {
47     freopen("buylow.in","r",stdin);
48     freopen("buylow.out","w",stdout);
49     int i,j;
50     scanf("%d\n",&N);
51     for(i = 0;i < N;i ++)
52     {
53         max[i] = 1;
54         scanf("%ld",&price[i]);
55         cnt[i].digit[0] = 1;
56         cnt[i].len = 1;
57     }
58     price[N] = 0;   //for simplicity
59     N ++;
60     for(i = 0;i < N;i ++)
61         for(j = i + 1;j < N;j ++)
62             if(price[j] == price[i])
63             {
64                 next[i] = j;
65                 break;
66             }
67
68     for(i = 0;i < N;i ++)
69         for(j = 0;j < i;j ++)
70         if(price[j] > price[i] && (next[j] == 0 || next[j] > i))
71         {
72             if(max[j] + 1 > max[i])
73             {
74                 max[i] = max[j] + 1;
75                 memcpy(&cnt[i],&cnt[j],sizeof(bignum));
76             }
77             else if(max[j] + 1 == max[i])
78             {
79                 cnt[i] = plus(cnt[i],cnt[j]);
80             }
81         }
82        
83     printf("%d ",max[N - 1] - 1);
84     for(i = cnt[N - 1].len - 1;i >= 0;i --)
85         printf("%d",cnt[N - 1].digit[i]);
86     printf("\n");
87     return 0;
88 }