對(duì)于楊氏矩陣，是一種很強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，它既可以用來當(dāng)堆，又可以用平衡樹的查詢方法。

?

最常見的三種操作就是：插入，刪除，查詢。

?

對(duì)于插入操作：

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;} }

我們調(diào)用Insert(1,INF,tmp);每一次插入從第一行行末開始做起。

?

對(duì)于楊氏矩陣的刪除操作，其實(shí)跟堆排序中的操作差不多，因?yàn)闂钍暇仃嚰瓤梢援?dāng)作堆又可以當(dāng)成平衡樹。

刪除操作是這樣的：設(shè)刪除的元素是x，那么我們先用楊氏矩陣中最大的元素max代替x，那么，我們從max處開始重

新調(diào)整楊氏矩陣，每次比較右邊和下邊的元素值，將max與較小值交換。

?

題目：給n個(gè)數(shù)(n<=5000),所有數(shù)都是1到255,你需要輸出最多能用多少數(shù)字構(gòu)成k個(gè)不下降子序列,子序列之間

? ? ?不能相交。

?

樣例輸入：
12 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//表示有12個(gè)數(shù)
1 3 4 2 3 4 1 2 2 3 3 2 ? ? ? ? //描述了這個(gè)序列

樣例輸出：
6 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //構(gòu)成1個(gè)不下降子序列最多可以用到6個(gè)數(shù)112233
9 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //構(gòu)成2個(gè)不下降子序列最多可以用到9個(gè)數(shù)112233和234
12 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//構(gòu)成3個(gè)不下降子序列最多可以用到全部12個(gè)數(shù)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; }

對(duì)于這個(gè)算法關(guān)于這道題目的正確性的簡要證明:

其實(shí)當(dāng)某一行有元素被踢到下一行的時(shí)候,在該行上的序列就可能已經(jīng)不是一個(gè)可行的序列了.但我們?yōu)槭裁礇]有修改

記錄這行元素個(gè)數(shù)的f[x][0] 呢.因?yàn)槲覀兊哪康氖堑玫揭粋€(gè)最大值.而且要被在我插入位置之后的那些數(shù)字并不是

不會(huì)被踢到下一行了而只是延后了而已.通過楊氏矩陣的堆性質(zhì),我們能夠保證踢下去的永遠(yuǎn)都是當(dāng)前最小的阻礙我插

進(jìn)去東西的那個(gè)數(shù).這里也巧妙地利用到了遞增序列的性質(zhì)。

?

?

總結(jié)

以上是生活随笔為你收集整理的杨氏矩阵的基本操作的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。