## HDOJ 5125 magic balls（树状数组优化）

2019年02月11日 ⁄ 综合 ⁄ 共 1493字 ⁄ 字号 评论关闭

```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);```

```#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;
}
{
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;
ans = max(ans, tmp);
if(k < m)
{
tmp = e[k + 1].sum(b[i] - 1) + 1;