C - The Battle of Chibi-Toy模板网

这篇具有很好参考价值的文章主要介绍了C - The Battle of Chibi。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题意：就是问你数组中长度为m的上升子序列(没说连续）有多少个。

1：可以想到状态表示dp[ i ][ j ] 代表以 a[i] 为结尾的且长度为 j 的严格单增子序列的数目，

那么状态计算就为 ,

那我们如果不优化直接写，一层n，一层 j 一层 k ，肯定会超时

2:考虑进行优化：
① 既然要优化求前缀和的速度，不妨对 dp[1∼n][1] 构造一个树状数组，对 dp[1∼n][2] 构造一个树状数组，⋯，对 dp[1∼n][m] 构造一个树状数组。这样一来，我要求 dp[i][j]。就可以再dp[1~n][j-1]z这颗树状数组里求前缀和了，这样一个前缀和就可以在 O(logn) 时间内完成。总时间复杂度变为 O(n2logn)。

②再想我们用树状数组数组时要以a[i]大小为下标，故要离散化一下

#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define xx first
#define yy second
#define endl "\n"
#define lowbit(x) x & (-x)
#define int long long
#define ull unsigned long long
#define pb push_back
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define Ysanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N = 5e5 + 10, M = 1010, inf = 0x3f3f3f3f, mod = 1e9 + 7, P = 13331;
const double eps = 1e-8;
int n, m;
int dp[M][M];
int a[N], l[N];
int cases;
//dp[i][j]=sum(dp[k][j-1])(k<i,a[k]<a[i],这个由add维护)
void add(int x, int y, int c)//相当于开了m个树状数组，每个数组数组维护一个长度的前缀和即dp[1~n][1],dp[1~n][2]....dp[1~n][m]
{
    for (int i = x; i <= n; i += lowbit(i))
        dp[i][y] = (dp[i][y] + c) % mod;
}
int query(int x, int y)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res = (res + dp[i][y]) % mod;
    return res;
}
void Unique()
{
    vector<int> s;
    for (int i = 1; i <= n; i++)
        s.pb(a[i]);
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    for (int i = 1; i <= n; i++)
    {
        int x = lower_bound(s.begin(), s.end(), a[i]) - s.begin() + 1;
        l[i] = x;
    }
}
void solve()
{
    memset(dp, 0, sizeof dp);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    Unique();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (j == 1)
                add(l[i], 1, 1);
            else
                add(l[i], j, query(l[i] - 1, j - 1));
        }
    }
    cout << "Case #" << ++cases << ":" << query(n, m) << endl;
}
signed main()
{
    Ysanqian;
    int T;
    // T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

还有另一种写法，开一层树状数组即可acwing上由这个解析文章来源地址https://www.toymoban.com/news/detail-636229.html

#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define xx first
#define yy second
#define endl "\n"
#define lowbit(x) x & (-x)
#define int long long
#define ull unsigned long long
#define pb push_back
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
// cout << "Case #" << ++cases << ": ";
#define Ysanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N = 1e6 + 10, M = 1010, inf = 0x3f3f3f3f, mod = 1e9 + 7, P = 13331;
const double eps = 1e-8;
int n, m;
int f[M][M];//表示以a[i]为结尾，长度为j的上升子序列的数量
int a[N], l[N], tr[N];
int cases;
void add(int x, int c)
{
    for (int i = x; i <= n; i += lowbit(i))
        tr[i] = (tr[i] + c) % mod;
}
int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res = (res + tr[i]) % mod;
    return res;
}
void Unique() // 离散化
{
    vector<int> s;
    for (int i = 1; i <= n; i++)
        s.pb(a[i]);
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    for (int i = 1; i <= n; i++)
    {
        int x = lower_bound(s.begin(), s.end(), a[i]) - s.begin() + 1;
        l[i] = x;
    }
}
void solve()
{
    cout << "Case #" << ++cases << ": ";
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    Unique();
    for (int i = 1; i <= n; i++) // 初始化第一层
        f[i][1] = 1;

    for (int j = 2; j <= m; j++) // 第一层已经算完了,我们改变循环的顺序，就可以只保留一棵树即可，为啥这样循环可以只开一棵树
    /*就在这做个解释吧，假设a[4]={20,30,40,10};离散化后大小为l[4]={2,3,4,1},
    f[1][1]=1;
    f[2][1]=1;初始化;   然后j=2这一层来说，首先清空tr数组，开始循环   
    f[3][1]=1;          i=1; f[1][2]可以由谁来转移呢，显然没有那就是0
    f[4][1]=1;          然后我们在l[1]这个位置上加上f[1][1],为下面得第二轮循环做准备
                        i=2; f[2][2]可以由谁来转移呢，显然没有那就是f[1][1]的数量,前提a[1]<a[2],故我们查询小于l[2]的数，刚好我们上一轮
                        l[1]加上了f[1][1],且l[2]>l[1],得以转移， 然后我们在l[2]这个位置上加上f[2][1],为下面得第三轮循环做准备
                        i=3;f[3][2]可以由谁来转移呢，显然没有那就是f[2][1]加上f[1][1]的数量,恰好我们前两轮都在相应得位置加上了，那么我们只需
                        询问l[1],l[2]是否小于l[3]就可以了，如果小于直接树状数组前缀和就把f[2][1]和f[1][1]加上了，
                        然后我们在l[3]这个位置上加上f[3][1],为下面得第三轮循环做准备
                        依次类推，可以看出我们的状态转移只会用到上一层，而我们这样先枚举j，正好解决了开m颗树的问题
    */
    {
        for (int i = 1; i <= n; i++)
            tr[i] = 0;
        for (int i = 1; i <= n; i++)
        {
                f[i][j] = query(l[i] - 1); // 查询小于l[i]的个数(我们把a[i]的值离散化为l[i]了，但是a[i]之间的大小关系并未发生改变)
            add(l[i], f[i][j - 1]);    // f[i][j]表示以a[i]结尾,长度为j的递增序列数量
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++)
        res = (res + f[i][m]) % mod;
    cout << res << endl;
}
signed main()
{
    Ysanqian;
    int T;
    // T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

到了这里，关于C - The Battle of Chibi的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！