Algoogle

Algorithm for Programming Contest

PKU 1952 BUY LOW, BUY LOWER

Category: PKU Tag: dp

BUY LOW, BUY LOWER

問題概要


解法


dp1[i] := i日目を最初に買った時の最長の長さ
dp2[i] := i日目を最初に買った時の最長の場合の数
これを最終日から見ていく.
また, 3 2 1 3 2 1のようなばあい, 最長は3 2 1というのが2つあるが区別しないので
3 1と出力しなければならない
これは最終日から見ていった時, すでにみた場所に同じ価格があったら古い方は消していけばいい

コード


(1952.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <algorithm>
#include <cstdio>
#include <set>

using namespace std;

int N, price[5010];
int dp1[5010], dp2[5010];

int main(){
    scanf("%d", &N);
    for(int i = 0; i < N; i++){
        scanf("%d", price + i);
        dp1[i] = dp2[i] = 1;
    }
    int len = 1;
    for(int i = N-1; i >= 0; i--){
        int mlen = 1, sum = 1;
        for(int j = i+1; j < N; j++)
            if(price[j] < price[i]){
                if(dp1[j] + 1 > mlen) {
                    mlen = dp1[j] + 1;
                    sum = dp2[j];
                }
                else if(dp1[j] + 1 == mlen) sum += dp2[j];
            }
            else if(price[i] == price[j])
                dp1[j] = dp2[j] = 0;
        dp1[i] = mlen;
        dp2[i] = sum;
        len = max(len, mlen);
    }
    int cnt = 0;
    for(int i = 0; i < N; i++)
        if(dp1[i] == len)
            cnt += dp2[i];
    printf("%d %d\n", len, cnt);
    return 0;
}

Comments