【20171026】Luogu P1108 低价购买

题目描述

“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(2^16范围内的正整数)，你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买；再低价购买”的原则。写一个程序计算最大购买次数。

这里是某支股票的价格清单：

日期 1 2 3 4 5 6 7 8 9 10 11 12

价格 68 69 54 64 68 64 70 67 78 62 98 87

最优秀的投资者可以购买最多4次股票，可行方案中的一种是：

日期 2 5 6 10

价格 69 68 64 62

输入输出格式
输入格式：

第1行: N (1 <= N <= 5000)，股票发行天数

第2行: N个数，是每天的股票价格。
输出格式：

输出文件仅一行包含两个数:最大购买次数和拥有最大购买次数的方案数(<=2^31)当二种方案“看起来一样”时（就是说它们构成的价格队列一样的时候）,这2种方案被认为是相同的。

输入输出样例
输入样例#1：复制
BUYLOW.IN
12
68 69 54 64 68 64 70 67 78 62 98 87
输出样例#1：复制
BUYLOW.OUT
4 2

不忙，
我们先定义几个量（初读可能很难理解，建议先向下看解题过程，再回头看量的定义）：
   a[i]表示 "原始序列的第[i]号元素"，
   d[i]表示 "以a[i]结尾的最长上升子序列的长度"，
   LIS[i]表示 "以a[i]结尾的最长上升子序列"，
       没看错，它是个序列恩，即LIS[i]={x,y,z,...,a[i]}，其中x<y<z<...<a[i]；
   c[i]表示 "以a[i]结尾的LIS方案数"（依题意，方案不可重复计数），
现在看题！

对于第一问——最长长度：
求最长上升子序列LIS（Longest Increasing Subsequence）的dp方程：
上升！上升！上升！上天~~
   则d[i]=max(d[j]+1)，j∈[1,n-1] && a[j]<a[i]，
   表示对于每一个a[i]，它都可以接到每一个a[j](保证a[j]<a[i])之后，长度加一，成为一个上升子序列；
   所以ans1=
   ="（每种长度）中的（最长者）”
   ="（每种"部分情况中最长长度"）中的（最长者）"
   ="（每个d[i]）中的（最长者）"
   =max(d[i])，i∈[1,n].②
However，题目要求我们求最长下降子序列（我喜欢叫ta LDS(Longest Decreasing Subsequence) ），
下降！下降！下降！啪~~
   则d'[i]=max(1,d'[j]+1)，j∈[1,n-1] && a[j]>a[i]; ①
   ans=max(d'[i])，i∈[1,n].

对于第二问——统计方案数（这里直接对下降子序列求解）：
   则c[i]=sum(c[j]),j∈[1,n-1] && a[j]>a[i] && d[j]+1==d[i]，③
       其中条件 "d[j]+1=d[i]" 表示 "我的a[i]是紧接在LDS[j]末尾的"
   但是，题目中要求 "去重" ，即 "包含同样方案的不同位置序列视为同一种序列"
   那么如果j<i && a[j]==a[i] && d[j]==d[i]，则"c[i]代表的方案必定包含着c[j]代表的方案"，
   根据③可知，c[i]与c[j]将被重复计算，这是不允许发生的，
   所以我们选择保留（排在后面的，包含c[j]的）c[i]，使c[j]=0即可.
   于是有c[j]=0,j∈[1,n-1] && a[j]==a[i] && d[j]==d[i]，④

ans2=sum(c[i]), i∈[1,n] && d[i]=ans1⑤

综上所述，解决此题，只需联立①②③④⑤求解即可：

d[i]    = max(d[j]+1)，   j∈[1,n-1] && a[j]>a[i]，①
ans1 = max(d[i])，      i∈[1,n]，②
c[i]    = sum(c[j]),       j∈[1,n-1] && a[j]>a[i] && d[j]+1==d[i]，③
c[j]    = 0,           j∈[1,n-1] && a[j]==a[i] && d[j]==d[i]，④
ans2 = sum(c[i]),           i∈[1,n] && d[i]=ans1，⑤

下面这代码求第一问没问题了，第二问还有错误，我回去改改

luogu53分代码如下——

code1:

 1 /*
 2 d[i]= max(d[j]+1)，    j∈[1,n-1]&&a[j]>a[i]，① 
 3 ans1 = max(d[i])，    i∈[1,n].② 
 4 c[i]=sum(c[j]),        j∈[1,n-1]&&a[j]>a[i]&&d[j]+1==d[i]，③ 
 5 c[j]=0,                j∈[1,n-1]&&a[j]==a[i]&&d[j]==d[i]，④
 6 ans2=sum(c[i]), i∈[1,n]&&d[i]=ans1⑤ 
 7 */
 8 #include<stdio.h>
 9 #include<string.h>
10 #define MAXN 5002
11 int n;
12 int a[MAXN],d[MAXN],c[MAXN];
13 int main()
14 {
15     memset(a,0,sizeof(a));
16     memset(d,0,sizeof(d));
17     memset(c,0,sizeof(c));
18     /*我的老师说可以用这种方法来将数组置0*/
19     
20     scanf("%d",&n);
21     int i,j;
22     int ans1,ans2;
23     for(i=1;i<=n;i++)
24     {
25         scanf("%d",&a[i]);
26     }
27         
28     ans1=ans2=0;
29     for(i=1;i<=n;i++)
30     {
31         d[i]=1;//a[i]本身就可以是一个长度为 1 的LDS 
32         for(j=1;j<i;j++)
33         {
34             if(d[j]+1>d[i]&&a[j]>a[i])
35                 d[i]=d[j]+1;
36         }
37         if(d[i]>ans1)
38             ans1=d[i];
39     }
40      
41     for(i=1;i<=n;i++)
42     {
43         for(j=1;j<i;j++)
44         {
45             if(a[j]>a[i]&&d[j]+1==d[i])
46                 c[i]+=c[j];
47             if(a[j]==a[i]&&d[j]==d[i])
48                 c[j]=0;
49         }
50         if(d[i]==ans1)
51             ans2+=c[i];
52         if(c[i]==0)//如果之前都没有LDS能以a[i]结尾的，那么就说明i自己是一个开头 
53             c[i]=1;//这个初始化的摆放位置非常有内涵，值得思考哦 
54     }
55         
56     printf("%d %d
",ans1,ans2);
57 }

错误处1（未考虑n==1的情况）：code1第50~53行调一下位置，拿到了73分

code2:

1 if(c[i]==0)//如果之前都没有LDS能以a[i]结尾的，那么就说明i自己是一个开头 
2     c[i]=1;//这个初始化的摆放位置非常有内涵，值得思考哦 
3 if(d[i]==ans1)
4     ans2+=c[i];