学步园

递推方程BC的题解讲得很清楚了：

if(a[i] > a[j])
    for(int k = 0; k <= j && k <= m; k++)
        dp[i][k][0] = max(dp[i][k][0], dp[j][k][0] + 1);
if(a[i] > b[j])
    for(int k = 1; k <= j && k <= m; k++)
        dp[i][k][0] = max(dp[i][k][0], dp[j][k][1] + 1);
if(b[i] > a[j])
    for(int k = 0; k <= j && k < m; k++)
        dp[i][k + 1][1] = max(dp[i][k + 1][1], dp[j][k][0] + 1);
if(b[i] > b[j])
    for(int k = 1; k <= j && k < m; k++)
        dp[i][k + 1][1] = max(dp[i][k + 1][1], dp[j][k][1] + 1);

但是这样会超时【其实直接递推也有过了的】

在找最大值的地方可以加优化：

对于花费同样的能量，第i个人，只需要搜索第1~i-1个人中的最大值，于是想到树状数组，可以很方便的查出1~x中的最值> <

但是树状数组如果存入的是最值，就只能越改越大；存最小值，就只能越改越小。求和无影响。

#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAXN 1010
struct BIT
{
    int c[MAXN * 2];
    int n;
    BIT() {}
    BIT(int _n)
    {
        n = _n;
        memset(c, 0, sizeof(c));
    }
    int lowbit(int x)
    {
        return x & (-x);
    }
    int sum(int i)
    {
        int ret = 0;
        while(i)
        {
            ret = max(ret, c[i]);
            i -= lowbit(i);
        }
        return ret;
    }
    void add(int i, int cmp)
    {
        while(i <= n)
        {
            c[i] = max(c[i], cmp);
            i += lowbit(i);
        }
    }
}e[MAXN];
int a[MAXN], b[MAXN], v[MAXN * 2], cnt, ans;

int b_srch(int vi)
{
    return lower_bound(v, v + cnt, vi) - v + 1;
}

int main()
{
//    freopen("5125.in", "r", stdin);

    int t, n, m;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; i++)
        {
            scanf("%d%d", a + i, b + i);
            v[2 * i] = a[i];
            v[2 * i + 1] = b[i];
        }

        sort(v, v + 2 * n);
        cnt = 0;
        for(int i = 0; i < 2 * n; i++)
            if(v[cnt] != v[i])
                v[++cnt] = v[i];
        cnt++;

        for(int i = 0; i < n; i++)
            a[i] = b_srch(a[i]), b[i] = b_srch(b[i]);

        ans = 0;
        for(int i = 0; i <= m; i++)
            e[i] = BIT(cnt);
        for(int i = 0; i < n; i++)
        {
            for(int k = 0; k <= m; k++)
            {
                int tmp = e[k].sum(a[i] - 1) + 1;
                e[k].add(a[i], tmp);
                ans = max(ans, tmp);
                if(k < m)
                {
                    tmp = e[k + 1].sum(b[i] - 1) + 1;
                    e[k].add(b[i], tmp);
                    ans = max(ans, tmp);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}