学步园

对于杨氏矩阵，是一种很强大的数据结构，它既可以用来当堆，又可以用平衡树的查询方法。

最常见的三种操作就是：插入，删除，查询。

对于插入操作：

void Insert(int x,int y,int num)
{
    y = min(y,a[x][0]);
    while(y > 0 && a[x][y] > num) y--;
    y++;
    if(a[x][y] == 0)
    {
        a[x][y] = num;
        a[x][0]++;
    }
    else
    {
        Insert(x+1,y,a[x][y]);
        a[x][y] = num;
    }
}

我们调用Insert(1,INF,tmp);每一次插入从第一行行末开始做起。

对于杨氏矩阵的删除操作，其实跟堆排序中的操作差不多，因为杨氏矩阵既可以当作堆又可以当成平衡树。

删除操作是这样的：设删除的元素是x，那么我们先用杨氏矩阵中最大的元素max代替x，那么，我们从max处开始重新调整杨氏

矩阵，每次比较右边和下边的元素值，将max与较小值交换。

题目：给n个数(n<=5000),所有数都是1到255,你需要输出最多能用多少数字构成k个不下降子序列,子序列之间不能相交。

样例输入：
12                                   //表示有12个数
1 3 4 2 3 4 1 2 2 3 3 2              //描述了这个序列

样例输出：
6                                    //构成1个不下降子序列最多可以用到6个数112233
9                                    //构成2个不下降子序列最多可以用到9个数112233和234
12                                   //构成3个不下降子序列最多可以用到全部12个数1344，2333和1222

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
const int N = 1005;
const int INF = ~0U>>1;

int a[N][N];

void Insert(int x,int y,int num)
{
    y = min(y,a[x][0]);
    while(y > 0 && a[x][y] > num) y--;
    y++;
    if(a[x][y] == 0)
    {
        a[x][y] = num;
        a[x][0]++;
    }
    else
    {
        Insert(x+1,y,a[x][y]);
        a[x][y] = num;
    }
}

int main()
{
    int n,tmp;
    scanf("%d",&n);
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&tmp);
        Insert(1,INF,tmp);
    }
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        ans += a[i][0];
        if(a[i][0] == 0) break;
        printf("%d\n",ans);
    }
    return 0;
}

对于这个算法关于这道题目的正确性的简要证明:

其实当某一行有元素被踢到下一行的时候,在该行上的序列就可能已经不是一个可行的序列了.但我们为什么没有修改记录这行

元素个数的f[x][0] 呢.因为我们的目的是得到一个最大值.而且要被在我插入位置之后的那些数字并不是不会被踢到下一行了

而只是延后了而已.通过杨氏矩阵的堆性质,我们能够保证踢下去的永远都是当前最小的阻碍我插进去东西的那个数.这里也巧妙

地利用到了递增序列的性质。