洛谷P1108 低价购买（最长下降子序列方案数）（int，long long等范围）

这道题用n方的算法会很好做

我一开始想的是nlogn的算法求方案数，

然后没有什么想法（实际上也可以做，但是我太弱了）
我们就可以根据转移方程来推方案数，只是把max改成加，很多动规题

都是这样，比如背包的方案数。

设f[i]为以i为结尾的方案数

当 b[j] + 1 == b[i] 且 a[j] > a[i]时，f[i] 加上f[j]

同时要去重，当b[i] == b[j] 且 a[i] == a[j]时，f[i]为0

另外int最大范围是2^31-1，按理来说这道题应该开longlong，但是可以ac，

说明数据比较弱。但是以后做其他题还是要注意

总结一波

int范围 -2^31 ~ 2^31-1

unsigned int 0 ~ 2 ^ 32 - 1

long long 范围 -2^63 ~ 2^63-1

unsigned long long 范围 0 ~ 2^64-1

#include<cstdio>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 5123;

int a[MAXN], b[MAXN], f[MAXN], n;

bool cmp(int a, int b)

{

    return a > b;

}

int main()

{

    scanf("%d", &n);

    REP(i, 0, n) scanf("%d", &a[i]);

    int ans1 = 0, ans2 = 0;

    REP(i, 0, n)

    {

        b[i] = 1;

        REP(j, 0, i)

            if(a[i] < a[j])

                b[i] = max(b[i], b[j] + 1);

        ans1 = max(ans1, b[i]);

    }

    REP(i, 0, n)

    {

        if(b[i] == 1) f[i] = 1;

        REP(j, 0, i)

        {

            if(b[j] + 1 == b[i] && a[j] > a[i])

                f[i] += f[j];

            else if(b[i] == b[j] && a[i] == a[j])

                f[i] = 0;

        }

        if(b[i] == ans1) ans2 += f[i];

    }

    printf("%d %d\n", ans1, ans2);

    return 0;

}

巴特西

洛谷P1108 低价购买（最长下降子序列方案数）（int，long long等范围）

最新文章

热门文章

巴特西

洛谷P1108 低价购买 （最长下降子序列方案数）（int，long long等 范围）

最新文章

热门文章

洛谷P1108 低价购买（最长下降子序列方案数）（int，long long等范围）