大致题意
给一个长度为 n 的序列 ai，现要求 k 条不上升子序列，使得他们的权值和最大。求最大值。 n的范围好像是1000
思路
容易想到拆点最大费用流，首先把每个点 i 拆成 2 个，i 向 i’ 连一条容量为 1 费用为 ai 的边，限制每个数字只能用一次，然后寻找 ai >= aj ，然后 i’ 向 j 连一条 容量为1 费用为 0 的边。最后起点终点连起来，然后再建一个超前起点se 连一条 容量为 k 费用为 0 的边，终点也可以一样搞一下。 然后我原来的spfa优化的费用流板子一直TLE，可见spfa真的死了，可能这个建图就是网格图？？ 然后上网上找了一个巨巨的djistra优化的板子，好像比较高级，有用势解决负权的功能，然后这里要求最大费用，所以要建负边，要多用用才知道这玩意。 有空研究研究。
代码
#include<bits/stdc++.h>
using namespace std
;
#define maxn 4005
#define maxm 1006
#define ll long long int
#define INF 0x3f3f3f3f
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
#define mem(a) memset(a,0,sizeof(a))
#define sqr(x) (x*x)
#define inf (ll)2e18+1
#define PI acos(-1)
#define mod 10007
#define auto(i,x) for(int i=head[x];i;i=ed[i].nxt)
#define ls x<<1
#define rs x<<1|1
ll
read(){
ll x
=0,f
=1ll;char ch
=getchar();
while(!isdigit(ch
)){if(ch
=='-')f
=-1;ch
=getchar();}
while(isdigit(ch
))x
=x
*10+ch
-'0',ch
=getchar();
return f
*x
;
}
int n
,m
,b
[maxn
],T
;
int s
,t
,se
,te
;
#include<functional>
typedef pair
<int, int> pii
;
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
){
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 main()
{
T
=read();
while(T
--){
n
=read();m
=read();
s
=2*n
+1;t
=s
+1;se
=s
+2;te
=s
+3;
init(te
);
inc(i
,1,n
)b
[i
]=read();
inc(i
,1,n
)addEdge(i
,i
+n
,1,-b
[i
]),addEdge(s
,i
,1,0),addEdge(i
+n
,t
,1,0);
inc(i
,1,n
)inc(j
,i
+1,n
)if(b
[i
]<=b
[j
])addEdge(i
+n
,j
,1,0);
addEdge(se
,s
,m
,0);addEdge(t
,te
,m
,0);
int ans
;
printf("%d\n",-MCMF(se
,te
,INF
,ans
));
}
return 0;
}
