题解 P2687 【[USACO4.3]逢低吸纳Buy Low, Buy Lower 】

· · 题解

写在前面

先安利一下自己的线性dp题单

这是题面

双倍经验(还不卡long long

正文

题面应该很清楚了，咱直接进入正题

购买股票的要求：价格必须比上一次底

第一问

看到问题的第一眼，就知道是个LIS板子，5000的数据，n^2也能过

for(int i = 1; i <= n; ++i){//板中板
        f[i] = 1;
        for(int j = 1; j < i; ++j){
            if(a[j] > a[i]){
                f[i] = max(f[i], f[j] + 1);
            }
        }
        ans = max(ans, f[i]);
    }
    printf("%lld ", ans);

第二问

统计方案数，乍一看有点难搞

线性递推一下，开一个数组s存方案数，用s[i]表示，长度为i时的方案数

显然，如果f[i]的长度比f[j]的长度长1，且a[i] < a[j],那么f[j]后面可以接一个元素，方案数也应该从f[j]时的方案累加过来

如果f[i]和f[j]一样，并且a[i] == a[j]那么它们属于同一种方案，把对应的s[i]赋成0即可

高精度

(毒瘤出题人卡我第九个点

long long直接爆，看到楼下许多都没有写高精而是直接卡数据点当然第一次我也卡了一下

作为一篇题解（咳咳，垃圾题解，我太蒻了

我还是要介绍一下高精写法的

（许多大佬都会用字符串高精，或者用double卡，但我不会）

那么对一个元素来说，一个空间不够用，给它开一串可以了吧

给需要高精的元素开成一个数组，每个数组存七位（几位都可），

在进行加法运算的时候，暴力枚举数组内的每个空间进行加和进位操作

需要注意的是，在最后输出的时候，可能某个元素里的位数不足七位（前导0），不要忘记输出前导0，

输出几个？什么时候输出？暴力判断就好了啊

详情见代码

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
const int MAXN = 5010;
const int mod = 10000000;
int n, ans = 0, ans2[11];
int a[MAXN];
int f[MAXN], s[MAXN][11];
bool flag;

int max(int x, int y){return x > y ? x : y; }

signed main()
{
    scanf("%ld", &n);
    for(int i = 1; i <= n; ++i) scanf("%ld", &a[i]);
    for(int i = 1; i <= n; ++i){
        f[i] = 1;
        for(int j = 1; j < i; ++j){
            if(a[j] > a[i]){
                f[i] = max(f[i], f[j] + 1);
            }
        }
        ans = max(ans, f[i]);
    }
    printf("%lld ", ans);

    for(int i = 1; i <= n; ++i){
        if(f[i] == 1) s[i][1] = 1;
        for(int j = 1; j < i; ++j){
            if(f[i] == f[j] + 1 && a[i] < a[j]){
                for(int k = 1; k <= 10; ++k){
                    s[i][k] += s[j][k];
                    s[i][k + 1] += s[i][k] / mod;
                    s[i][k] %= mod;
                }
            }
            else if(f[i] == f[j] && a[i] == a[j]){
                for(int k = 1; k <= 10; ++k) s[i][k] = 0;
            }
        }
        if(f[i] == ans) {
            for(int k = 1; k <= 10; ++k){
                ans2[k] += s[i][k];
                ans2[k + 1] += ans2[k] / mod;
                ans2[k] %= mod;
            }
        }
    }

    for(int i = 10; i >= 1; --i){
        if(!ans2[i] && !flag) continue;
        else flag = true;
        if(flag){
            int cnt = 0;
            for(int k = 7; k >= 1; --k){
                if((ans2[i] / (pow(10, k - 1))) == 0){
                    cnt++;
                }
                else break;
            }
            while(cnt--)printf("0");
            printf("%lld", ans2[i]);
        }
    }

    return 0;
}