[洛谷P1108]低价购买

记录一种常见的求方案数的思路——基于dp数组的dp。

#include <bits/stdc++.h>
#define MAXN 5001
using namespace std;

int n;
int ansa,ansb;

int a[MAXN];
int dpa[MAXN];
int dpb[MAXN];

int main() {
    ios::sync_with_stdio(false);

    cin >> n;

    for ( int i = 1; i <= n; ++i ) 
        cin >> a[i];

    for ( int i = 1; i <= n; ++i ) {
        for ( int j = 1; j < i; ++j )
            if ( a[i] < a[j] )
                dpa[i] = max(dpa[i], dpa[j] + 1);

        ansa = max(ansa, dpa[i]);
    }
    ansa += 1;

    for ( int i = 1; i <= n; ++i ) {
        if ( dpa[i] == 0 )
            dpb[i] = 1;

        for ( int j = 1; j < i; ++j ) {
            if ( dpa[i] == dpa[j] + 1 && a[i] < a[j] )
                dpb[i] += dpb[j];

            if ( dpa[i] == dpa[j] && a[i] == a[j] )
                dpb[i] = 0;
        }

        if ( dpa[i] == ansa - 1 )
            ansb += dpb[i];
    }

    cout << ansa << ' ' << ansb << endl;

    return 0;
}
阿里云服务器
Last modification:July 23rd, 2019 at 07:35 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏

Leave a Comment