ICPC2019南京站网络赛 F Greedy Sequence

题目链接：https://nanti.jisuanke.com/t/41303

题意：给你一个包含N个数字的全排列，构成n个序列，每个序列以i开头，且之后的元素必须比它小，并且相邻元素在原排列中位置的绝对值不能大于K

分析：好简单的题啊。。。竟然没想出出来，直接贪心记忆化就好的。。还好队友用主席树过了，我好菜啊。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
struct node{
    int val,id;
    bool operator < (const node &x) const {
        return val<x.val;
    }
}a[maxn];
int num[maxn];
int main(){
    int T;scanf("%d",&T);
    while(T--){
        int n,k;scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i].val);
            a[i].id=i;
        }
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++){
            int len=1;
            for(int j=i-1;j>=1;j--){
                if(abs(a[i].id-a[j].id)<=k){
                    len+=num[j];
                    break;
                }
            }
            num[i]=len;
            printf("%d",len);
            if(i==n)printf("
");
            else printf(" ");
        }
    } 
    return 0;
}