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種方案被認為是相同的。

輸入輸出樣例

BUYLOW.IN
12
68 69 54 64 68 64 70 67 78 62 98 87

BUYLOW.OUT
4 2

先探索一下樣例，最大購買次數為4次，共有2中方案，分別是69 68 64 62、69 68 67 62。

我們發現，這道題實際上是在一個數列中選出一個序列，使得這個序列是下降序列（即序列中的任意一個數必須大於它後面的任何一個數），且要使這個序列的長度最長。但是這道題要輸出總的方案數，這就需要對原有的求解過程做一些變動。求方案總數最主要的是要剔除重覆方案。當第2行N個數其中有兩個以上價格相同時，可能就會產生重覆方案。產生重覆方案時，顯然後麵價格的要比前面的更優，因為以後面的價格結尾的最長下降序列的總數肯定不會比前一個少，而且其方案必定囊括了前面這個價格的所有方案。因此，在解題過程中，我們就可以只考慮相同價格中後面的那個。推廣開來，如果當前狀態之前存在重覆的狀態，我們只要考慮離當前狀態位置最近的那一個即可。

設f[i]表示到第i天，能夠買的最大次數，顯然有：f[1]=1；f[i]=max{f[j]+1}(1<=j<=i-1，且ok[j]=1)，ok[j]=1表示相同價格時，該位置更優。

 1 #include<stdio.h>
 2 #include<string.h>
 3 bool ok[50010];
 4 int a[5010],b[5010],f[5010];
 5 int n,i,j,k,max,num;
 6 int main()
 7 {
 8     scanf("%d",&n);
 9     for(i=1;i<=n;i++)
10         scanf("%d",&a[i]);
11     b[1]=1;
12     f[1]=1;
13     for(i=2;i<=n+1;i++)
14     {
15         max=0;
16         f[i]=1;
17         for(j=i-1;j>=1;j--)
18             if(a[i]<a[j])
19                 if(b[j]>max)//b[j]表示以第j天結尾的最大購買次數 
20                 {
21                     max=b[j];
22                     memset(ok,1,sizeof(ok));
23                     ok[a[j]]=0;
24                     f[i]=f[j];
25                 }
26                 else
27                     if(b[j]==max && ok[a[j]])
28                     {
29                         ok[a[j]]=0;
30                         f[i]+=f[j];
31                     }
32         b[i]=max+1;
33     }
34     printf("%d %d",b[n+1]-1,f[n+1]);
35 }