K Subsequence

Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2103    Accepted Submission(s): 491

 

Problem Description

Master QWsin is dating with Sindar. And now they are in a restaurant, the restaurant has n dishes in order. For each dish, it has a delicious value ai. However, they can only order k times. QWsin and Sindar have a special ordering method, because they believe that by this way they can get maximum happiness value.

Specifically, for each order, they will choose a subsequence of dishes and in this subsequence, when i<j, the subsequence must satisfies ai≤aj. After a round, they will get the sum of the subsequence and they can't choose these dishes again. 

Now, master QWsin wants to know the maximum happiness value they can get but he thinks it's too easy, so he gives the problem to you. Can you answer his question?

 

Input

There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:

First line contains two positive integers n and k which are separated by spaces.

Second line contains n positive integer a1,a2,a3...an represent the delicious value of each dish.


1≤T≤5

1≤n≤2000

1≤k≤10

1≤ai≤1e5

Output

Only an integer represent the maximum happiness value they can get.

 

Sample Input

1 9 2 5 3 2 1 4 2 1 4 6

Sample Output

22

 

题意：有一个序列，现在有 k 次操作，每一次可以选取一个不递减的序列，并将这个序列的和加到答案上，一个数只能选一次。问最后答案最大是多少。

思路：n^2 建图 （a[i] <= a[j] 就建费用为0，容量为1的边），然后把一个数a[i]，拆成左右两个点（i 和 n + i），费用是 -a[i]，容量是1，然后汇点到超级汇点容量是 k （这样就能保证取 k 次），跑一遍最小费用最大流，取费用的相反数即是答案。。。！！这个题卡spfa版费用流，用dij版直接过。

Code：

#include<bits/stdc++.h>
#define debug(x) cout << "[" << #x <<": " << (x) <<"]"<< endl
#define pii pair<int,int>
#define clr(a,b) memset((a),b,sizeof(a))
#define rep(i,a,b) for(int i = a;i < b;i ++)
#define pb push_back
#define MP make_pair
#define LL long long
#define ull unsigned LL
#define ls i << 1
#define rs (i << 1) + 1
#define fir first
#define sec second
#define CLR(a) while(!(a).empty()) a.pop()

using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 1e4;
struct edge {
	int to, capacity, cost, rev;
	edge() {}
	edge(int to, int _capacity, int _cost, int _rev):
	    to(to), capacity(_capacity), cost(_cost), rev(_rev) {}
};

struct Min_Cost_Max_Flow {
	int V, H[maxn + 5], dis[maxn + 5], PreV[maxn + 5], PreE[maxn + 5];
	vector<edge> G[maxn + 5];
	void Init(int n) {
		V = n;
		for (int i = 0; i <= V; ++i)G[i].clear();
	}
	void Add_Edge(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 Min_cost_max_flow(int s, int t, int f, int& flow) {
		int res = 0; fill(H, H + 1 + V, 0);
		while (f) {
			priority_queue <pii, vector<pii>, greater<pii> > q;
			fill(dis, dis + 1 + V, 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.capacity > 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];
						PreV[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 = PreV[v])d = min(d, G[PreV[v]][PreE[v]].capacity);
			f -= d; flow += d; res += d*H[t];
			for (int v = t; v != s; v = PreV[v]) {
				edge& e = G[PreV[v]][PreE[v]];
				e.capacity -= d;
				G[v][e.rev].capacity += d;
			}
		}
		return res;
	}
};

int a[maxn];

int main() {
    int t; scanf("%d",&t);
    while(t --){
        int n,k; scanf("%d%d",&n,&k);
        rep(i,1,n + 1) scanf("%d",&a[i]);
        Min_Cost_Max_Flow MCMF;
        MCMF.Init(2 * n + 2);
        for(int i = 1;i <= n;++ i){
            MCMF.Add_Edge(0,i,1,0);
            MCMF.Add_Edge(i,n + i,1,-a[i]);
            MCMF.Add_Edge(n + i,2 * n + 1,1,0);
            for(int j = i + 1;j <= n;++ j){
                if(a[i] <= a[j])
                    MCMF.Add_Edge(n + i,j,1,0);
            }
        }
        MCMF.Add_Edge(2 * n + 1,2 * n + 2,k,0);
        printf("%d\n",-MCMF.Min_cost_max_flow(0,2 * n + 2,INF,k));
    }
    return 0;
}