新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:30000KB
安く買おう。以前より安く買おう。
問題 
「安く買おう」という言葉は、牛株式市場において成功するための公式のようになっている。ここでは高名な投資家の考えに従って、次のように考えよう:
「安く買おう。以前より安く買おう。」
あなたが株式を買うときは、以前にあなたが買った値段よりも安く買わなければならない。以前より安い値段で買った回数が多ければ多いほど良い！あなたの目的は、価格を安くしながら何回株式を買うことができるかを調べることである。
あなたは各時点における株式の価格(正の16-bit整数)が与えられる。各日について株式を買うかどうかを決定できる。ただし、株式を買うときは、以前に買ったときより値段が安くなっている必要がある。株式を買う回数を最大化するためにいつ株式を買えばいいかを特定するプログラムを書け。
次に株式の価格の例を示す:
Day 1 2 3 4 5 6 7 8 9 10 11 12
Price 68 69 54 64 68 64 70 67 78 62 98 87
最良の投資家(この問題においては誰しもが最良の投資家でなければならないが)ならば、前の購入より安くなるようにしながら株式を最多で4回購入することができる。4回購入する1つの例(他にもあるかもしれない)は:
Day 2 5 6 10
Price 69 68 64 62
入力
- 1行目: 何日分の株式価格が与えられるかを表す整数N(1 <= N <= 5000)
- 2行目以降: 各日における株式価格をあらわす整数列が、1行に10個ずつ空白を区切りとして書かれている。
出力
1行に2つの整数を出力せよ:
- 順々に下がっていく株式価格の列のうち最長のものの長さ
- そのような列が何通りあるか(31bitの範囲内であることが保証される)
解の個数を数えるとき、2つの解が同じであるとは、減少する数字の列の表記が一致することを指す。つまり、2つの価格列の「見ためが同じ」ならば同じ解とみなす。よって、株式を買った日が異なる場合でも、買った価格の列が等しい場合は、同じ解として数える。
入力例
12 68 69 54 64 68 64 70 67 78 62 98 87
出力例
4 2
出典
USACO 2002 February
