股票市場usaco
❶ 什麼是動態規劃如何運用動態規劃解決實際問題
我也不明白，找一下看有用沒。
動態規劃演算法的應用
一、動態規劃的概念
近年來，涉及動態規劃的各種競賽題越來越多，每一年的NOI幾乎都至少有一道題目需要用動態規劃的方法來解決；而競賽對選手運用動態規劃知識的要求也越來越高，已經不再停留於簡單的遞推和建模上了。
要了解動態規劃的概念，首先要知道什麼是多階段決策問題。
1. 多階段決策問題
如果一類活動過程可以分為若干個互相聯系的階段，在每一個階段都需作出決策(採取措施)，一個階段的決策確定以後，常常影響到下一個階段的決策，從而就完全確定了一個過程的活動路線，則稱它為多階段決策問題。
各個階段的決策構成一個決策序列，稱為一個策略。每一個階段都有若干個決策可供選擇，因而就有許多策略供我們選取，對應於一個策略可以確定活動的效果，這個效果可以用數量來確定。策略不同，效果也不同，多階段決策問題，就是要在可以選擇的那些策略中間，選取一個最優策略，使在預定的標准下達到最好的效果.
2．動態規劃問題中的術語
階段：把所給求解問題的過程恰當地分成若干個相互聯系的階段，以便於求解，過程不同，階段數就可能不同．描述階段的變數稱為階段變數。在多數情況下，階段變數是離散的，用k表示。此外，也有階段變數是連續的情形。如果過程可以在任何時刻作出決策，且在任意兩個不同的時刻之間允許有無窮多個決策時，階段變數就是連續的。
在前面的例子中，第一個階段就是點A，而第二個階段就是點A到點B，第三個階段是點B到點C，而第四個階段是點C到點D。
狀態：狀態表示每個階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉移，也稱為不可控因素。在上面的例子中狀態就是某階段的出發位置，它既是該階段某路的起點，同時又是前一階段某支路的終點。
在前面的例子中，第一個階段有一個狀態即A，而第二個階段有兩個狀態B1和B2，第三個階段是三個狀態C1，C2和C3，而第四個階段又是一個狀態D。
過程的狀態通常可以用一個或一組數來描述，稱為狀態變數。一般，狀態是離散的，但有時為了方便也將狀態取成連續的。當然，在現實生活中，由於變數形式的限制，所有的狀態都是離散的，但從分析的觀點，有時將狀態作為連續的處理將會有很大的好處。此外，狀態可以有多個分量(多維情形)，因而用向量來代表；而且在每個階段的狀態維數可以不同。
當過程按所有可能不同的方式發展時，過程各段的狀態變數將在某一確定的范圍內取值。狀態變數取值的集合稱為狀態集合。
無後效性：我們要求狀態具有下面的性質：如果給定某一階段的狀態，則在這一階段以後過程的發展不受這階段以前各段狀態的影響，所有各階段都確定時，整個過程也就確定了。換句話說，過程的每一次實現可以用一個狀態序列表示，在前面的例子中每階段的狀態是該線路的始點，確定了這些點的序列，整個線路也就完全確定。從某一階段以後的線路開始，當這段的始點給定時，不受以前線路（所通過的點）的影響。狀態的這個性質意味著過程的歷史只能通過當前的狀態去影響它的未來的發展，這個性質稱為無後效性。
決策：一個階段的狀態給定以後，從該狀態演變到下一階段某個狀態的一種選擇（行動）稱為決策。在最優控制中，也稱為控制。在許多間題中，決策可以自然而然地表示為一個數或一組數。不同的決策對應著不同的數值。描述決策的變數稱決策變數，因狀態滿足無後效性，故在每個階段選擇決策時只需考慮當前的狀態而無須考慮過程的歷史。
決策變數的范圍稱為允許決策集合。
策略：由每個階段的決策組成的序列稱為策略。對於每一個實際的多階段決策過程，可供選取的策略有一定的范圍限制，這個范圍稱為允許策略集合。允許策略集合中達到最優效果的策略稱為最優策略。
給定k階段狀態變數x(k)的值後，如果這一階段的決策變數一經確定，第k+1階段的狀態變數x(k+1)也就完全確定，即x(k+1)的值隨x(k)和第k階段的決策u(k)的值變化而變化，那麼可以把這一關系看成(x(k)，u(k))與x(k+1)確定的對應關系，用x(k+1)=Tk(x(k),u(k))表示。這是從k階段到k+1階段的狀態轉移規律，稱為狀態轉移方程。
最優性原理:作為整個過程的最優策略，它滿足：相對前面決策所形成的狀態而言，餘下的子策略必然構成「最優子策略」。
最優性原理實際上是要求問題的最優策略的子策略也是最優。讓我們通過對前面的例子再分析來具體說明這一點：從A到D，我們知道，最短路徑是AB1C2D，這些點的選擇構成了這個例子的最優策略，根據最優性原理，這個策略的每個子策略應是最優：AB1C2是A到C2的最短路徑，B1C2D也是B1到D的最短路徑……——事實正是如此，因此我們認為這個例子滿足最優性原理的要求。
[編輯本段]動態規劃練習題
USACO
2.2 Subset Sums
題目如下：
對於從1到N的連續整集合合，能劃分成兩個子集合，且保證每個集合的數字和是相等的。
舉個例子，如果N=3，對於{1，2，3}能劃分成兩個子集合，他們每個的所有數字和是相等的：
{3}and {1,2}
這是唯一一種分發（交換集合位置被認為是同一種劃分方案，因此不會增加劃分方案總數）
如果N=7，有四種方法能劃分集合{1，2，3，4，5，6，7}，每一種分發的子集合各數字和是相等的:
{1,6,7} and {2,3,4,5} {注 1+6+7=2+3+4+5}
{2,5,7} and {1,3,4,6}
{3,4,7} and {1,2,5,6}
{1,2,4,7} and {3,5,6}
給出N，你的程序應該輸出劃分方案總數，如果不存在這樣的劃分方案，則輸出0。程序不能預存結果直接輸出。
PROGRAM NAME: subset
INPUT FORMAT
輸入文件只有一行，且只有一個整數N
SAMPLE INPUT (file subset.in)
7
OUTPUT FORMAT
輸出劃分方案總數，如果不存在則輸出0。
SAMPLE OUTPUT (file subset.out)
4
參考程序如下（c語言）：
#include <fstream>
using namespace std;
const unsigned int MAX_SUM = 1024;
int n;
unsigned long long int dyn[MAX_SUM];
ifstream fin ("subset.in");
ofstream fout ("subset.out");
int main() {
fin >> n;
fin.close();
int s = n*(n+1);
if (s % 4) {
fout << 0 << endl;
fout.close ();
return ;
}
s /= 4;
int i, j;
dyn [0] = 1;
for (i = 1; i <= n; i++)
for (j = s; j >= i; j--)
dyn[j] += dyn[j-i];
fout << (dyn[s]/2) << endl;
fout.close();
return 0;
}
USACO 2.3
Longest Prefix
題目如下：
在生物學中，一些生物的結構是用包含其要素的大寫字母序列來表示的。生物學家對於把長的序列分解成較短的（稱之為元素的）序列很感興趣。
如果一個集合 P 中的元素可以通過串聯（允許重復；串聯，相當於 Pascal 中的 「+」 運算符）組成一個序列 S ，那麼我們認為序列 S 可以分解為 P 中的元素。並不是所有的元素都必須出現。舉個例子，序列 ABABACABAAB 可以分解為下面集合中的元素：
{A, AB, BA, CA, BBC}
序列 S 的前面 K 個字元稱作 S 中長度為 K 的前綴。設計一個程序，輸入一個元素集合以及一個大寫字母序列，計算這個序列最長的前綴的長度。
PROGRAM NAME: prefix
INPUT FORMAT
輸入數據的開頭包括 1..200 個元素（長度為 1..10 ）組成的集合，用連續的以空格分開的字元串表示。字母全部是大寫，數據可能不止一行。元素集合結束的標志是一個只包含一個 「.」 的行。集合中的元素沒有重復。接著是大寫字母序列 S ，長度為 1..200,000 ，用一行或者多行的字元串來表示，每行不超過 76 個字元。換行符並不是序列 S 的一部分。
SAMPLE INPUT (file prefix.in)
A AB BA CA BBC
.
ABABACABAABC
OUTPUT FORMAT
只有一行，輸出一個整數，表示 S 能夠分解成 P 中元素的最長前綴的長度。
SAMPLE OUTPUT (file prefix.out)
11
示常式序如下：
#include <stdio.h>
/* maximum number of primitives */
#define MAXP 200
/* maximum length of a primitive */
#define MAXL 10
char prim[MAXP+1][MAXL+1]; /* primitives */
int nump; /* number of primitives */
int start[200001]; /* is this prefix of the sequence expressible? */
char data[200000]; /* the sequence */
int ndata; /* length of the sequence */
int main(int argc, char **argv)
{
FILE *fout, *fin;
int best;
int lv, lv2, lv3;
if ((fin = fopen("prim.in", "r")) == NULL)
{
perror ("fopen fin");
exit(1);
}
if ((fout = fopen("prim.out", "w")) == NULL)
{
perror ("fopen fout");
exit(1);
}
/* read in primitives */
while (1)
{
fscanf (fin, "%s", prim[nump]);
if (prim[nump][0] != '.') nump++;
else break;
}
/* read in string, one line at a time */
ndata = 0;
while (fscanf (fin, "%s", data+ndata) == 1)
ndata += strlen(data+ndata);
start[0] = 1;
best = 0;
for (lv = 0; lv < ndata; lv++)
if (start[lv])
{ /* for each expressible prefix */
best = lv; /* we found a longer expressible prefix! */
/* for each primitive, determine the the sequence starting at
this location matches it */
for (lv2 = 0; lv2 < nump; lv2++)
{
for (lv3 = 0; lv + lv3 < ndata && prim[lv2][lv3] &&
prim[lv2][lv3] == data[lv+lv3]; lv3++)
;
if (!prim[lv2][lv3]) /* it matched! */
start[lv + lv3] = 1; /* so the expanded prefix is also expressive */
}
}
/* see if the entire sequence is expressible */
if (start[ndata]) best = ndata;
fprintf (fout, "%i\n", best);
return 0;
}
USACO 3.1
Score Inflation
題目如下：
我們試著設計我們的競賽以便人們能盡可能的多得分,這需要你的幫助。
我們可以從幾個種類中選取競賽的題目,這里的一個"種類"是指一個競賽題目的集合,解決集合中的題目需要相同多的時間並且能得到相同的分數。
你的任務是寫一個程序來告訴USACO的職員,應該從每一個種類中選取多少題目,使得解決題目的總耗時在競賽規定的時間里並且總分最大。
輸入包括競賽的時間,M(1 <= M <= 10,000)和N,"種類"的數目1 <= N <= 10,000。
後面的每一行將包括兩個整數來描述一個"種類":
第一個整數說明解決這種題目能得的分數(1 <= points <= 10000),第二整數說明解決這種題目所需的時間(1 <= minutes <= 10000)。
你的程序應該確定我們應該從每個"種類"中選多少道題目使得能在競賽的時間中得到最大的分數。
來自任意的"種類"的題目數目可能任何非負數(0或更多)。
計算可能得到的最大分數。
PROGRAM NAME: inflate
INPUT FORMAT
第 1 行: M, N--競賽的時間和題目"種類"的數目。
第 2-N+1 行: 兩個整數:每個"種類"題目的分數和耗時。
SAMPLE INPUT (file inflate.in)
300 4
100 60
250 120
120 100
35 20
OUTPUT FORMAT
單獨的一行包括那個在給定的限制里可能得到的最大的分數。
SAMPLE OUTPUT (file inflate.out)
605
{從第2個"種類"中選兩題，第4個"種類"中選三題}
示常式序如下：
#include <fstream.h>
ifstream fin("inflate.in");
ofstream fout("inflate.out");
const short maxm = 10010;
long best[maxm], m, n;
void
main()
{
short i, j, len, pts;
fin >> m >> n;
for (j = 0; j <= m; j++)
best[j] = 0;
for (i = 0; i < n; i++) {
fin >> pts >> len;
for (j = len; j <= m; j++)
if (best[j-len] + pts > best[j])
best[j] = best[j-len] + pts;
}
fout << best[m] << endl; // 由於數組元素不減，末元素最大
}
USACO 3.3
A Game
題目如下：
有如下一個雙人游戲:N(2 <= N <= 100)個正整數的序列放在一個游戲平台上，兩人輪流從序列的兩端取數，取數後該數字被去掉並累加到本玩家的得分中，當數取盡時，游戲結束。以最終得分多者為勝。
編一個執行最優策略的程序，最優策略就是使自己能得到在當前情況下最大的可能的總分的策略。你的程序要始終為第二位玩家執行最優策略。
PROGRAM NAME: game1
INPUT FORMAT
第一行: 正整數N, 表示序列中正整數的個數。
第二行至末尾: 用空格分隔的N個正整數（大小為1-200）。
SAMPLE INPUT (file game1.in)
6
4 7 2 9
5 2
OUTPUT FORMAT
只有一行，用空格分隔的兩個整數: 依次為玩家一和玩家二最終的得分。
SAMPLE OUTPUT (file game1.out)
18 11
參考程序如下：
#include <stdio.h>
#define NMAX 101
int best[NMAX][2], t[NMAX];
int n;
void
readx () {
int i, aux;
freopen ("game1.in", "r", stdin);
scanf ("%d", &n);
for (i = 1; i <= n; i++) {
scanf ("%d", &aux);
t = t[i - 1] + aux;
}
fclose (stdin);
}
inline int
min (int x, int y) {
return x > y ? y : x;
}
void
solve () {
int i, l;
for (l = 1; l <= n; l++)
for (i = 1; i + l <= n + 1; i++)
best[l%2] = t[i + l - 1] - t[i - 1] - min (best[i + 1][(l - 1) % 2],
best[(l - 1) % 2]);
}
void writex () {
freopen ("game1.out", "w", stdout);
printf ("%d %d\n", best[1][n % 2], t[n] - best[1][n % 2]);
fclose (stdout);
}
int
main () {
readx ();
solve ();
writex ();
return 0;
}
USACO 3.4
Raucous Rockers
題目如下：
你剛剛得到了流行的「破鑼搖滾」樂隊錄制的尚未發表的N(1 <= N <= 20)首歌的版權。你打算從中精選一些歌曲，發行M(1 <= M <= 20)張CD。每一張CD最多可以容納T(1 <= T <= 20)分鍾的音樂，一首歌不能分裝在兩張CD中。
不巧你是一位古典音樂迷，不懂如何判定這些歌的藝術價值。於是你決定根據以下標准進行選擇：
歌曲必須按照創作的時間順序在CD盤上出現。
選中的歌曲數目盡可能地多。
PROGRAM NAME: rockers
INPUT FORMAT
第一行： 三個整數：N, T, M.
第二行： N個整數，分別表示每首歌的長度，按創作時間順序排列。
SAMPLE INPUT (file rockers.in)
4 5 2
4 3 4 2
OUTPUT FORMAT
一個整數，表示可以裝進M張CD盤的樂曲的最大數目。
SAMPLE OUTPUT (file rockers.out)
3
參考程序如下：
#include <stdio.h>
#define MAX 25
int dp[MAX][MAX][MAX], length[MAX];
int
main ()
{
FILE *in = fopen ("rockers.in", "r");
FILE *out = fopen ("rockers.out", "w");
int a, b, c, d, best, numsongs, cdlength, numcds;
fscanf (in, "%d%d%d", &numsongs, &cdlength, &numcds);
for (a = 1; a <= numsongs; a++)
fscanf (in, "%d", &length[a]);
best = 0;
for (a = 0; a < numcds; a++)/*當前cd */
for (b = 0; b <= cdlength; b++) /* 已過的時間*/
for (c = 0; c <= numsongs; c++) { /* 上一曲*/
for (d = c + 1; d <= numsongs; d++) { /* 下一曲*/
if (b + length[d] <= cdlength) {
if (dp[a][c] + 1 > dp[a][b + length[d]][d])
dp[a][b + length[d]][d] = dp[a][c] + 1;
}
else {
if (dp[a][c] + 1 > dp[a + 1][length[d]][d])
dp[a + 1][length[d]][d] = dp[a][c] + 1;
}
}
if (dp[a][c] > best)
best = dp[a][c];
}
fprintf (out, "%d\n", best);
return 0;
}
USACO
4.3 Buy Low, Buy Lower
「逢低吸納」是炒股的一條成功秘訣。如果你想成為一個成功的投資者，就要遵守這條秘訣:
"逢低吸納,越低越買"
這句話的意思是：每次你購買股票時的股價一定要比你上次購買時的股價低.按照這個規則購買股票的次數越多越好，看看你最多能按這個規則買幾次。
給定連續的N天中每天的股價。你可以在任何一天購買一次股票，但是購買時的股價一定要比你上次購買時的股價低。寫一個程序，求出最多能買幾次股票。
以下面這個表為例, 某幾天的股價是:
天數 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
PROGRAM NAME: buylow
INPUT FORMAT
第1行: N (1 <= N <= 5000), 表示能買股票的天數。
第2行以下: N個正整數 (可能分多行) ，第i個正整數表示第i天的股價. 這些正整數大小不會超過longint(pascal)/long(c++).
SAMPLE INPUT (file buylow.in)
12
68 69 54 64 68 64 70 67
78 62 98 87
OUTPUT FORMAT
只有一行，輸出兩個整數：
能夠買進股票的天數
長度達到這個值的股票購買方案數量
在計算解的數量的時候，如果兩個解所組成的字元串相同，那麼這樣的兩個解被認為是相同的（只能算做一個解）。因此，兩個不同的購買方案可能產生同一個字元串，這樣只能計算一次。
SAMPLE OUTPUT (file buylow.out)
4 2
參考程序如下：
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef struct BIGNUM *bignum_t;
struct BIGNUM
{
int val;
bignum_t next;
};
int num[5000];
int len[5000];
int nlen;
bignum_t cnt[5000];
bignum_t get_big(void)
{
static bignum_t block;
static int size = 0;
if (size == 0)
{
block = (bignum_t)malloc(sizeof(*block)*128);
size = 128;
}
size--;
return block++;
}
/*初始化高精度數*/
void init_big(bignum_t *num, int val)
{
*num = get_big();
/* initialize */
(*num)->val = val;
(*num)->next = NULL;
}
void add(bignum_t a, bignum_t b)
{
int c; /* carry */
c = 0;
while (b || c)
{
a->val += c;
if (b) a->val += b->val;
/* if a->val is too large, we need to carry */
c = (a->val / 1000000);
a->val = (a->val % 1000000);
if (b) b = b->next;
if (!a->next && (b || c))
{ /* allocate if we need to */
a->next = get_big();
a = a->next;
a->val = 0;
a->next = NULL;
} else a = a->next;
}
}
void out_num(FILE *f, bignum_t v)
{
if (v->next)
{
out_num(f, v->next);
fprintf (f, "%06i", v->val);
}
else
fprintf (f, "%i", v->val);
}
int main(int argc, char **argv)
{
FILE *fout, *fin;
int lv, lv2;
int c;
int max;
int l;
bignum_t ans;
if ((fin = fopen("buylow.in", "r")) == NULL)
{
perror ("fopen fin");
exit(1);
}
if ((fout = fopen("buylow.out", "w")) == NULL)
{
perror ("fopen fout");
exit(1);
}
fscanf (fin, "%d", &nlen);
for (lv = 0; lv < nlen; lv++)
fscanf (fin, "%d", &num[lv]);
/* 用DP計算最大長度*/
for (lv = 0; lv < nlen; lv++)
{
max = 1;
for (lv2 = lv-1; lv2 >= 0; lv2--)
if (num[lv2] > num[lv] && len[lv2]+1 > max) max = len[lv2]+1;
len[lv] = max;
}
for (lv = 0; lv < nlen; lv++)
{
if (len[lv] == 1) init_big(&cnt[lv], 1);
else
{
init_big(&cnt[lv], 0);
l = -1;
max = len[lv]-1;
for (lv2 = lv-1; lv2 >= 0; lv2--)
if (len[lv2] == max && num[lv2] > num[lv] && num[lv2] != l)
add(cnt[lv], cnt[lv2]);
l = num[lv2];
}
}
}
/* 找最長串*/
max = 0;
for (lv = 0; lv < nlen; lv++)
if (len[lv] > max) max = len[lv];
init_big(&ans, 0);
l = -1;
for (lv = nlen-1; lv >= 0; lv--)
if (len[lv] == max && num[lv] != l)
{
add(ans, cnt[lv]);
l = num[lv];
}
/* output answer */
fprintf (fout, "%i ", max);
out_num(fout, ans);
fprintf (fout, "\n");
return 0;
}
動態規劃作為一種重要的信息學競賽演算法，具有很強的靈活性。以上提供的是一些入門練習題，深入的學習還需要逐步積累經驗。
❷ 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[i]不為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開始循環
type super=array[1..16] of longint;
var i,n,max,now,qi,j:longint;
h:array[1..3,0..5001] of longint;
st:array[0..5001] of integer;
c:array[0..5001] of Super;
ans,ch:string;
procere swap(var a,b:longint);
begin
if a=b then exit;
a:=a xor b;
b:=a xor b;
a:=a xor b;
end;
//
procere Super_inc(var a,b:Super);
var i,jin:longint;
begin
jin:=0;
for i:=1 to 16 do
begin
jin:=a[i]+b[i]+jin;
a[i]:=jin mod 10000;
jin:=jin div 10000;
end;
end;
//
procere CALC_H3;
var l,r,mid,i,last:longint;
q:array[0..5001] of integer;
begin
last:=0;
for i:=1 to n do
begin
l:=0;
r:=last+1;
while r-l>1 do
begin
mid:=(l+r) shr 1;
if q[mid]>h[2,i] then l:=mid
else r:=mid;
end;
if r>last then inc(last);
q[r]:=h[2,i];
h[3,i]:=l+1;
end;
end;
//
procere Qsort(p,l,r:longint);
var i,j,mid:longint;
begin
i:=l;
j:=r;
mid:=h[p,(l+r) shr 1];
repeat
while h[p,i]<mid do inc(i);
while h[p,j]>mid do dec(j);
if i<=j then
begin
swap(h[1,i],h[1,j]);
swap(h[2,i],h[2,j]);
swap(h[3,i],h[3,j]);
inc(i);
dec(j);
end;
until i>j;
if i<r then Qsort(p,i,r);
if j>l then Qsort(p,l,j);
end;
//
begin
assign(input,'buylow.in');
reset(input);
assign(output,'buylow.out');
rewrite(output);
readln(n);
for i:=1 to n do read(h[2,i]);
for i:=1 to n do h[1,i]:=i;
CAlC_H3;
Qsort(3,1,n);
//
st[1]:=1;
now:=1;
for i:=2 to n do
if h[3,i]>now then
begin inc(now);
st[now]:=i;
end;
st[now+1]:=n+1;
for i:=1 to now do
Qsort(2,st[i],st[i+1]-1);
//
qi:=1;
h[3,n+1]:=0;
for i:=2 to n+1 do
if not((h[2,i]=h[2,i-1])and(h[3,i]=h[3,i]))
then
begin Qsort(1,qi,i-1);
qi:=i;
end;
//
fillchar(c,sizeof(c),0);
c[0][1]:=1;
st[0]:=0;
h[2,n+1]:=0;
h[2,0]:=maxlongint;
h[1,n+1]:=n+1;
h[3,n+1]:=h[3,n]+1;
for i:=1 to n+1 do
begin
now:=-1;
for j:=st[h[3,i]]-1 downto st[h[3,i]-1] do
if h[2,j]<=h[2,i] then break else
if (h[2,j]<>now)and(h[2,j]>h[2,i])and(h[1,j]<h[1,i])
then begin Super_inc(c[i],c[j]);
now:=h[2,j];
end;
end;
//
for i:=63 downto 1 do if c[n+1][i]<>0 then break;
str(c[n+1][i],ch);
ans:=ans+ch;
for j:=i-1 downto 1 do
begin
str(c[n+1][j],ch);
for qi:=1 to 4-length(ch) do ch:='0'+ch;
ans:=ans+ch;
end;
//
writeln(h[3,n],' ',ans);
close(output);
end.