题意：

有\(n\)个数\(a_1\cdots a_n\)，现要你给出\(k\)个不相交的非降子序列，使得和最大。

思路：

费用流建图，每个点拆点，费用为\(-a[i]\)，然后和源点连边，和后面非降的数连边，源点和超级源点连一条容量\(k\)的边，跑费用流。

用\(spfa\)费用流\(TLE\)，这里因为不会出现负环，所以用\(Dijkstra\)优化。

代码：

/*******

dijkstra优化费用流模板

*******/

//不能有负环

#include<functional>    //C++编译需要头文件

typedef pair<int, int> pii;//first保存最短距离，second保存顶点的编号

struct edge {

    int to, cap, cost, rev; //终点,容量（指残量网络中的）,费用,反向边编号

    edge() {}

    edge(int to, int _cap, int _cost, int _rev):to(to), cap(_cap), cost(_cost), rev(_rev) {}

};

int V;          //顶点数

int h[maxn];    //顶点的势

int dis[maxn];  //最短距离

int prevv[maxn];//最短路中的父结点

int pree[maxn]; //最短路中的父边

vector<edge> G[maxn];   //图的邻接表

void init(int n) {

    V = n;

    for(int i = 0; i <= V; ++i) G[i].clear();

}

void addEdge(int from, int to, int cap, int cost){

    G[from].push_back(edge(to, cap, cost, G[to].size()));

    G[to].push_back(edge(from, 0, -cost, G[from].size() - 1));

}

int MCMF(int s, int t, int f, int &flow){   //f为最多能流多少

    int res = 0;

    for(int i = 0; i < 1 + V; i++) h[i] = 0;

    while(f){

        priority_queue<pii, vector<pii>, greater<pii> > q;

        for(int i = 0; i < 1 + V; i++) dis[i] = INF;

        dis[s] = 0; q.push(pii(0, s));

        while(!q.empty()) {

            pii now = q.top(); q.pop();

            int v = now.second;

            if(dis[v] < now.first) continue;

            for(int i = 0; i < G[v].size(); ++i) {

                edge &e = G[v][i];

                if(e.cap > 0 && dis[e.to] > dis[v] + e.cost + h[v] - h[e.to]){

                    dis[e.to] = dis[v] + e.cost + h[v] - h[e.to];

                    prevv[e.to] = v;

                    pree[e.to] = i;

                    q.push(pii(dis[e.to], e.to));

                }

            }

        }

        if(dis[t] == INF) break;

        for(int i = 0; i <= V; ++i) h[i] += dis[i];

        int d = f;

        for(int v = t; v != s; v = prevv[v]) d = min(d, G[prevv[v]][pree[v]].cap);

        f -= d; flow += d; res += d * h[t];

        for(int v = t; v != s; v = prevv[v]) {

            edge &e = G[prevv[v]][pree[v]];

            e.cap -= d;

            G[v][e.rev].cap += d;

        }

    }

    return res;

}

#include<map>

#include<set>

#include<cmath>

#include<cstdio>

#include<stack>

#include<ctime>

#include<vector>

#include<queue>

#include<cstring>

#include<string>

#include<sstream>

#include<iostream>

#include<algorithm>

typedef long long ll;

using namespace std;

const int maxn = 5000 + 5;

const int INF = 0x3f3f3f3f;

const ll MOD = 1e9 + 7;

using namespace std;

//不能有负环

#include<functional>    //C++编译需要头文件

typedef pair<int, int> pii;//first保存最短距离，second保存顶点的编号

struct edge {

    int to, cap, cost, rev; //终点,容量（指残量网络中的）,费用,反向边编号

    edge() {}

    edge(int to, int _cap, int _cost, int _rev):to(to), cap(_cap), cost(_cost), rev(_rev) {}

};

int V;          //顶点数

int h[maxn];    //顶点的势

int dis[maxn];  //最短距离

int prevv[maxn];//最短路中的父结点

int pree[maxn]; //最短路中的父边

vector<edge> G[maxn];   //图的邻接表

void init(int n) {

    V = n;

    for(int i = 0; i <= V; ++i) G[i].clear();

}

void addEdge(int from, int to, int cap, int cost){

    G[from].push_back(edge(to, cap, cost, G[to].size()));

    G[to].push_back(edge(from, 0, -cost, G[from].size() - 1));

}

int MCMF(int s, int t, int f, int &flow){   //f为最多能流多少

    int res = 0;

    for(int i = 0; i < 1 + V; i++) h[i] = 0;

    while(f){

        priority_queue<pii, vector<pii>, greater<pii> > q;

        for(int i = 0; i < 1 + V; i++) dis[i] = INF;

        dis[s] = 0; q.push(pii(0, s));

        while(!q.empty()) {

            pii now = q.top(); q.pop();

            int v = now.second;

            if(dis[v] < now.first) continue;

            for(int i = 0; i < G[v].size(); ++i) {

                edge &e = G[v][i];

                if(e.cap > 0 && dis[e.to] > dis[v] + e.cost + h[v] - h[e.to]){

                    dis[e.to] = dis[v] + e.cost + h[v] - h[e.to];

                    prevv[e.to] = v;

                    pree[e.to] = i;

                    q.push(pii(dis[e.to], e.to));

                }

            }

        }

        if(dis[t] == INF) break;

        for(int i = 0; i <= V; ++i) h[i] += dis[i];

        int d = f;

        for(int v = t; v != s; v = prevv[v]) d = min(d, G[prevv[v]][pree[v]].cap);

        f -= d; flow += d; res += d * h[t];

        for(int v = t; v != s; v = prevv[v]) {

            edge &e = G[prevv[v]][pree[v]];

            e.cap -= d;

            G[v][e.rev].cap += d;

        }

    }

    return res;

}

int a[maxn];

int main(){

    int T;

    scanf("%d", &T);

    while(T--){

        int n, k;

        scanf("%d%d", &n, &k);

        init(n * 2 + 5);

        int s = n * 2 + 1, e = n * 2 + 2;

        int ss = n * 2 + 3, se = n * 2 + 4;

        for(int i = 1; i <= n; i++){

            scanf("%d", &a[i]);

            addEdge(i, i + n, 1, -a[i]);

            addEdge(s, i, 1, 0);

            addEdge(i + n, e, 1, 0);

        }

        for(int i = 1; i <= n; i++){

            for(int j = i + 1; j <= n; j++){

                if(a[i] <= a[j])

                    addEdge(i + n, j, 1, 0);

            }

        }

        addEdge(ss, s, k, 0);

        addEdge(e, se, k, 0);

        int flow;

        printf("%d\n", -MCMF(ss, se, INF, flow));

    }

    return 0;

}