题意：求a数组的LIS，但是加了一个条件，为了LIS最大 b[i] a[i]可以交换。最多交换m次；
思路：我们令dp[i][j][l]表示i在最长上升子序列中，已经损失j点能量,第i个人转换了ai和bi的最长上升子序列的数目，可以得到方程 dp[i][j][0]=max{dp[k][j][0](a[k]<a[i])+1,dp[k][j][1](b[k]<a[i])+1},dp[i][j][1]=max(dp[k][j-1][0](a[k]<b[i])+1,dp[k][j-1][1](b[k]<b[i])+1)。这样是n^2k的，我们换个思路，即从k能转移到哪些i，我们先将体积离散化，再用m颗线段树来维护已损失j点能量的情况下体积为某数的最长上升子序列。这样可以做到nlgnk，不过线段树常数写的很大的话还是会TLE，考虑到求最大值实际上是求1~x的最大值，这样我们可以通过常数非常小的树状数组来解决。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 20000
using namespace std; int n,m;
int a[],b[];
int dp[][][];
int c[][];
int f[],cnt; inline int Find(int xx)
{
return lower_bound(f,f+cnt,xx)-f+;
} inline void insert(int *c,int x,int cc)
{
for(; x<=cnt; x+=x&-x)
{
c[x]=max(c[x],cc);
}
} inline int get_max(int *c,int x)
{
int ans=;
for( ; x; x-=x&-x)
{
ans=max(ans,c[x]);
}
return ans;
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{ int n,m;
scanf("%d%d",&n,&m);
cnt=;
for(int i=;i<=n;++i)
{
scanf("%d%d",a+i,b+i);
f[cnt++]=a[i];
f[cnt++]=b[i];
}
sort(f,f+cnt);
cnt=unique(f,f+cnt)-f;
for(int i=;i<=n;++i)
{
a[i]=Find(a[i]);
b[i]=Find(b[i]);
}
memset(c,,sizeof(c));
int ans=;
for(int i=;i<=n;++i)
{
for(int j=;j<=min(m,i);++j)
{
dp[i][j][]=get_max(c[j],a[i]-)+;
ans=max(ans,dp[i][j][]);
if(j)
{
dp[i][j][]=get_max(c[j-],b[i]-)+;
ans=max(ans,dp[i][j][]);
}
}
for(int j=;j<=min(m,i);++j)
{
insert(c[j],a[i],dp[i][j][]);
if(j) insert(c[j],b[i],dp[i][j][]);
}
}
printf("%d\n",ans);
}
return ;
}