Home

# 序列

# 题目描述

Ciry 决定尝试无平方因子二元合数接龙，规则如下:
现有 nn 个不超过 10610^6 的合数，每个均可表示为 a=pqa=pq ( p,qp,q 为两个互异素数)。 若 a=p1q1(p1<q1)a=p_1 q_1 (p_1 < q_1) , b=p2q2(p2<q2)b=p_2 q_2(p_2 < q_2) ，当且仅当 q1=p2q_1 = p_2 时 bb 能接在 aa 后面。 请问从给定的这 nn 个数中选数接龙，最长可以形成一个包含多少数的接龙序列？

# 解题思路

题目保证了分解出的两个质数的顺序，所以可以按照较小的质数排序，这样在连边的时候就会比较方便找点，暴力连边，连完是一张 DAG，直接拓扑排序跑 DP 就好。

# Code

#define Aniciry Meteorshower_Y
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N = 5e4+10;
const int A = 1e6+10;
struct Meteorshower_Y{
    Meteorshower_Y(){
    freopen("chain.in", "r", stdin);
    freopen("chain.out", "w", stdout);
}};Meteorshower_Y Aniciry;
struct node{int p, q;
    friend bool operator<(node a, node b){
        if(a.p != b.p) return a.p < b.p;
        return a.q < b.q;
    }
};
int n, a[N], f[N], d[N];
int cnt, p[A], vis[A];
node P[N]; vector<int> to[N];
auto solve() -> int;
auto preform(int n) -> void;
auto main() -> signed
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i += 1)
        scanf("%d", &a[i]);
    preform(1e6);
    printf("%d", solve());
    return 0;
}
auto preform(int A) -> void
{
    for(int i = 2; i <= A; i += 1)
    {
        if(!vis[i]) p[++cnt] = i;
        for(int j = 1; j <= cnt and i*p[j] <= A; j += 1)
        {
            vis[i*p[j]] = 1;
            if(i%p[j] == 0) break;
        }
    }
    for(int i = 1; i <= n; i += 1)
        for(int j = 1; j <= cnt; j += 1)
            if(!(a[i]%p[j])){P[i] = {p[j], a[i]/p[j]}; break;}
    sort(P+1, P+n+1, [](node a, node b){return a.p <= b.p;});
    for(int i = 1; i <= n; i += 1)
    {
        int l = lower_bound(P+1, P+n+1, (node){P[i].q, 0})-P;
        int r = upper_bound(P+1, P+n+1, (node){P[i].q, A})-P;
        for(int j = l; j < r; j += 1) to[i].push_back(j), d[j] += 1;
    }
}
auto solve() -> int
{
    int ans = 1, x; queue<int> q;
    for(int i = 1; i <= n; i += 1)
        if(!d[i]) q.push(i), f[i] = 1;
    while(!q.empty())
    {
        x = q.front(); q.pop();
        for(int y: to[x])
        {
            f[y] = max(f[y], f[x]+1);
            if(!(d[y] -= 1)) q.push(y);
        }
    }
    for(int i = 1; i <= n; i += 1)
        ans = max(ans, f[i]);
    return ans;
}

# 生成最小树

# 题目描述

你有一个含 nn 个点，mm 条边的图。现在选出一棵生成树，你每次可以选择树上一条边使其边权 −1-1，问至少需要操作多少次之后这棵树会成为图的最小生成树。
保证图完全连通且不含重边。

第一行输入两个数 nn, mm，分别表示图的点数和边数；(1≤n≤10000,1≤m≤100000)(1 \le n \le 10000, 1 \le m \le 100000)
之后 mm 行，每行三个数 uu, vv, ww，表示从点 uu 到点 vv 的连边权值为 ww；
之后 n−1n-1 行，每行两个数 aa, bb，表示选定生成树的每条边。

# 解题思路

若给定的生成树为最小生成树的一种方案，那么非树边 u→vu \to v 的权值要大于等于树上 u→vu \to v 这一条链上的所有边权权值，所有我们可以将给定的生成树轻重链剖分，线段树维护一下链最大值，支持单点修改，然后枚举每一条边计算贡献就好（为了防止一条边被修改多次导致复杂度被卡，可以将所有的边按权值从小到大排序）

# Code

#define Aniciry Meteorshower_Y
#include<algorithm>
#include<iostream>
#include<utility>
#include<cstdio>
#include<map>
#define Pair pair<int, int> 
using namespace std;
typedef long long ll;
struct Meteorshower_Y{
    Meteorshower_Y(){
    freopen("mintree.in", "r", stdin);
    freopen("mintree.out", "w", stdout);
}};Meteorshower_Y Anciry;
const int N = 1e4+10;
const int M = 1e5+10;
namespace HLDT
{
    struct edge{
        int to, next;
    }a[M<<1];
    int head[N], cnt, tim;
    int f[N], w[N], siz[N], son[N];
    int id[N], aid[N], top[N], dep[N];
    auto dfs1(int x, int fa) -> void;
    auto dfs2(int x, int tp) -> void;
    auto query(int x, int y) -> Pair;
    auto solve(int x, int y, int w) -> void;
    auto add_edge(int from, int to) -> void;    
}
namespace LafT{
    struct tree{
        int l, r;
        Pair mx;
    }tr[N<<2];
    auto build(int l, int r, int i) -> void;
    auto modify(int x, int k, int i) -> void;
    auto querymax(int l, int r, int i) -> Pair;
}
int n, m, u, v, w; ll ans;
struct E{int u, v, w;}e[M];
map<pair<int, int>, int> mp;
auto main() -> signed
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i += 1)
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    for(int i = 1; i < n; i += 1)
    {
        scanf("%d%d", &u, &v);
        HLDT::add_edge(u, v); mp[Pair(u, v)] = 1;
        HLDT::add_edge(v, u); mp[Pair(v, u)] = 1;
    }
    HLDT::dfs1(1, 0); HLDT::dfs2(1, 1);
    for(int i = 1; i <= m; i += 1) 
        if(mp.count(pair<int, int>{e[i].u,e[i].v}))
            (HLDT::dep[e[i].u] < HLDT::dep[e[i].v])
                ?(HLDT::w[e[i].v]=e[i].w):(HLDT::w[e[i].u]=e[i].w);
    sort(e+1, e+m+1, [&](E a, E b){return a.w <= b.w;});
    LafT::build(1, n, 1);
    for(int i = 1; i <= m; i += 1)
        HLDT::solve(e[i].u, e[i].v, e[i].w);
    printf("%lld", ans);
    return 0;
}
namespace HLDT
{
    auto dfs1(int x, int fa) -> void
    {
        f[x] = fa; siz[x] = 1; dep[x] = dep[fa]+1;
        for(int i = head[x], y; i; i = a[i].next)
        {
            if(y = a[i].to, y == fa) continue;
            dfs1(y, x); siz[x] += siz[y];
            if(siz[y] > siz[son[x]]) son[x] = y;
        }
    }
    auto dfs2(int x, int tp) -> void
    {
        id[x] = ++tim; aid[tim] = x; top[x] = tp;
        if(!son[x]) return ; dfs2(son[x], tp);
        for(int i = head[x], y; i; i = a[i].next)
            if(y = a[i].to, y != f[x] and y != son[x]) dfs2(y, y);   
    }
    auto solve(int x, int y, int w) -> void
    {
        static Pair node;
        while(w < (node = query(x, y)).first)
        {
            ans += node.first-w;
            LafT::modify(node.second, w, 1);
        }
    }
    auto query(int x, int y) -> Pair
    {
        Pair ans = {0, 0};
        while(top[x] != top[y])
        {
            if(dep[top[x]] < dep[top[y]]) swap(x, y);
            ans = max(ans, LafT::querymax(id[top[x]], id[x], 1));
            x = f[top[x]];
        }
        if(id[x] == id[y]) return ans;
        if(id[x] > id[y]) swap(x, y);
        return max(ans, LafT::querymax(id[x]+1, id[y], 1));
    }
    auto add_edge(int from, int to) -> void
    {
        cnt += 1;
        a[cnt].to = to;
        a[cnt].next = head[from];
        head[from] = cnt;
    }
}
namespace LafT
{
    #define ls(i) (i<<1)
    #define rs(i) (i<<1|1)
    auto build(int l, int r ,int i) -> void
    {
        using namespace HLDT;
        tr[i].l = l; tr[i].r = r;
        if(l ==  r) return (void)(tr[i].mx = {HLDT::w[aid[l]], l});
        int mid = (l+r)>>1;
        build(l, mid, ls(i));
        build(mid+1, r, rs(i));
        tr[i].mx = max(tr[ls(i)].mx, tr[rs(i)].mx);
    }
    auto modify(int x, int k, int i) -> void
    {
        if(tr[i].l > x or tr[i].r < x) return ;
        if(tr[i].l == x and tr[i].r == x) 
            return (void)(tr[i].mx = {k, tr[i].l});
        modify(x, k, ls(i));
        modify(x, k, rs(i));
        tr[i].mx = max(tr[ls(i)].mx, tr[rs(i)].mx);
    }
    auto querymax(int l, int r, int i) -> Pair
    {
        if(tr[i].l > r or tr[i].r < l) return {0, 0};
        if(tr[i].l >= l and tr[i].r <= r) return tr[i].mx;
        return max(querymax(l, r, ls(i)), querymax(l, r, rs(i)));
    }
}

# 互质序列

# 题目描述

给出两个数 AA, BB， 问有多少个序列满足以下条件：

  1. 序列是递增的。
  2. 所有数字属于区间 [A,B][A,B] （包括 AA 和 BB ， B−A≤100B − A \le 100 ）。
  3. 序列中的所有数字两两互质
    其中，1≤A,B,≤1018,B−A≤1001 \le A, B, \le 10^{18}, B-A \le 100

# 解题思路

根据欧几里得辗转相除法我们可以知道，AA 到 BB 的数两两之间的最大公约数不超过 100100，而 100100 以内的质数只有 2525 个，所以可以对质数进行状压，一个根据题意，一个质数因子不能在两个数里同时出现，所以选择一种质数的组合的方案数求和实际上是枚举其补集的子集方案数的和。
直接 DP 的时间复杂度是 O(n2k)O(n 2^k)，其中 n=A−Bn = A-B，kk 为质数个数，在这里取 k=25k = 25， 会 TLE。因为在所有数中只出现一次的质数不会有重复贡献，所以把它们都除去，剩下的质数就少了，就可以过了。

# Code

#define Aniciry Meteorshower_Y 
#include<algorithm>
#include<iostream>
#include<cstdio>
#define cnt 25
using namespace std;
typedef  long long ll;
const int N = 1e2+06;
struct Meteorshower_Y{
    Meteorshower_Y(){
    freopen("rlprime.in", "r", stdin);
    freopen("rlprime.out", "w", stdout);
}};Meteorshower_Y Aniciry;
int n, m, st[N], vis[N], p[cnt+1]; 
ll A, B, ans, f[1<<26]; 
int P[cnt+1] = { 0, 2, 3, 5, 7, 11, 
                13, 17, 19, 23, 29, 
                31, 37, 41, 43, 47, 
                53, 59, 61, 67, 71,
                73, 79, 83, 89, 97};
auto dfs(int x) -> void;
signed main()
{
    scanf("%lld%lld", &A, &B);
    for(ll i = A; i <= B; i += 1)
        for(int j = 1; j <= cnt; j += 1)
            if(i%P[j] == 0) vis[j] += 1;
            
    for(int i = 1; i <= cnt; i += 1)
        if(vis[i] > 1) p[++m] = P[i];
    
    
    for(ll i = A; i <= B; i += 1)
        for(int j = 1; j <= m; j += 1)
            if(i%p[j] == 0) st[i-A] |= 1<<(j-1);
            
    int K = (1<<m)-1;
    f[0] = 1;
    for(ll i = A; i <= B; i += 1)
    {
        int s = K^st[i-A];
        for(int j = s; j; j = (j-1)&s)
            f[st[i-A]|j] += f[j];
        f[st[i-A]] += f[0];
    }
    for(int i = 0; i <= K; i += 1) ans += f[i];
    printf("%lld", ans-1);
    return 0;
}

# 鬼鬼的序列

# 题目描述

鬼鬼想找一种序列：向这个序列 aa 中加上不多于 kk 个数，使这个新的数列排序后可以得到一个公差为 dd 的等差序列。鬼鬼给你了一个由 nn 个整数组成的数列 aa 。你的任务是找到它的最长子串，使它是鬼鬼想找的序列。

n,k≤2×105,0≤d≤109,−109≤ai≤109n,k \le 2 \times 10^5, 0 \le d \le 10^9, -10^9 \le a_i \le 10^9。

# 解题思路

考虑暴力做法，枚举区间的左右端点，一段区间是否合法要看:

  1. 所有数在对 dd 取模后是否相同
  2. 是否有重复的数字出现
  3. kk 个数是否能补上等差数列中缺少的项

首项为 aa，末项为 bb, 公差为 dd 的等差数列的项数为 b−ad+1\frac{b-a}{d}+1

可以对于序列全部元素先除以个 dd，用线段树一个经典的套路，枚举右端点，维护左端点，除完 dd 之后项数就是自区间的极差加一。
得到合法区间判断式子 maxa−mina+1≤r−l+1+kmaxa - mina + 1 \le r-l+1 + k，
移项，得
maxa−mina+l≤r+kmaxa-mina + l \le r+k
所以线段树和单调栈维护极差，然后线段树二分找满足条件的最小左端点就可以了（不合法的左端点直接赋值 ∞\infty 就不会影响查询了。

# Code

#define Aniciry Neteorshower_Y
#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 2e5+10;
const int inf = 1e7;
typedef long long ll;
// 此处省略快读
struct Meteorshower_Y{
    Meteorshower_Y(){
    freopen("seq.in", "r", stdin);
    freopen("seq.out", "w", stdout);   
}};Meteorshower_Y Aniciry;
namespace LafTree
{
    struct tree{
        int l, r;
        ll val, lz;
    }tr[N<<2];
    auto build(int l, int r, int i) -> void;
    auto add(int l, int r, ll k, int i) -> void;
    auto query(int k, int i) -> int;
    auto pushdown(int i) -> void;
}using namespace LafTree;
int n, k, d, p, L, R, a[N], b[N];
int mx[N], mi[N], tp1, tp2;
unordered_map<int, int> mp;
inline auto solve() -> void;
int main()
{
    read(n, k, d);
    if(d == 0) return solve(), 0;
    for(int i = 1; i <= n; i += 1)
        read(a[i]), a[i] += 1e9, b[i] = a[i]/d;
    for(int i = 1; i <= n; i += 1)mp[a[i]] = 0;
    LafTree::build(1, n, 1); L = R = 1;
    mx[1] = mi[1] = 1, tp1 = tp2 = 1;
    for(int i = 2; i <= n; i += 1)
    {
        while(tp1 and b[i] > b[mx[tp1]]) LafTree::add(mx[tp1-1]+1, mx[tp1], b[i]-b[mx[tp1]], 1), tp1 -= 1; mx[++tp1] = i;
        while(tp2 and b[i] < b[mi[tp2]]) LafTree::add(mi[tp2-1]+1, mi[tp2], b[mi[tp2]]-b[i], 1), tp2 -= 1; mi[++tp2] = i;
        if((a[i]%d) != (a[i-1]%d)) LafTree::add(1, i-1, inf, 1); LafTree::add(1, mp[a[i]], inf, 1); mp[a[i]] = i;
        int r = i, l = LafTree::query(k+r, 1); if(r-l > R-L) R = r, L = l;
    }
    printf("%d %d", L, R);
    return 0;
    
    return 0;
}
inline auto solve() -> void
{
    int l = 0; a[0] = -1;
    for(int i = 1; i <= n; i += 1) read(a[i]);
    for(int i = 1; i <= n; i += 1)
    {
        if(a[i] == a[l]) {if(i-l > R-L) R = i, L = l;}
        else l = i;
    }
    printf("%d %d", L, R);
}
namespace LafTree
{
    #define ls(i) (i<<1)
    #define rs(i) (i<<1|1)
    auto build(int l, int r, int i) -> void
    {
        tr[i].l = l;
        tr[i].r = r;
        if(l == r) return (void)(tr[i].val = l);
        int mid = (l+r)>>1;
        build(l, mid, ls(i));
        build(mid+1, r, rs(i));
        tr[i].val = min(tr[ls(i)].val, tr[rs(i)].val);
    }
    auto add(int l, int r, ll k, int i) -> void
    {
        if(tr[i].l > r or tr[i].r < l) return ;
        if(tr[i].l >= l and tr[i].r <= r) 
        {
            tr[i].lz += k;
            tr[i].val += k;
            return ;
        }
        pushdown(i);
        add(l, r, k, ls(i));
        add(l, r, k, rs(i));
        tr[i].val = min(tr[ls(i)].val, tr[rs(i)].val);
    }
    auto query(int k, int i) -> int
    {
        if(tr[i].l == tr[i].r) return tr[i].l;
        pushdown(i);
        if(tr[ls(i)].val <= k) return query(k, ls(i));
        return query(k, rs(i));
    }
    auto pushdown(int i) -> void
    {
        if(tr[i].lz == 0) return ;
        tr[ls(i)].lz += tr[i].lz;
        tr[rs(i)].lz += tr[i].lz;
        tr[ls(i)].val += tr[i].lz;
        tr[rs(i)].val += tr[i].lz;
        tr[i].lz = 0;
    }
}

# PolarSea 与 边割集（cut）

# 题目描述

给定一课 nn 个点的无向树，边带权，树上节点有三种状态：无归属、属于 SolarPea、属于 PolarSea。
SolarPea 和 PolarSea 想断掉一些边，使得对于每一对点，若 xx 属于 PolarSea，yy 属于 SolarPea，则 xx 和 yy 不连通。
求断掉的边的最小权值和。

# 解题思路

考虑从底向上树形 dp。
f(i,0)f(i,0) 表示做完 ii 的子树后，ii 既不与 aa 中的点相连，也不与 bb 中的点相连的最小花费。
f(i,1)f(i,1) 表示做完 ii 的子树后，ii 只与 aa 中的点相连的最小花费。
f(i,2)f(i,2) 表示做完 ii 的子树后，ii 只与 bb 中的点相连的最小花费。
转移时讨论一下是否删边即可。时间复杂度为 O(n)O(n)。

当然，如果你不想推式子，可以和我一样网络流硬干。

# Code

#define Aniciry Meteorshower_Y
#include<iostream>
#include<climits>
#include<cstring>
#include<utility>
#include<cstdio>
#include<queue>
using namespace std;
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
namespace Netflow
{
    struct edge{
        int from, to;
        int flow, next;
    }a[N<<3];
    int head[N], cnt = 1, s, t;
    int vis[N], cur[N], maxflow, nowflow;
    inline auto solve() -> int;
    inline auto bfs(int s, int t) -> int;
    inline auto dinic(int s, int flow) -> int;
    inline auto build(int u, int v, int w) -> void;
    inline auto add_edge(int from, int to, int flow) -> void;
    inline auto Add_edge(int from, int to, int flow) -> void;
}
int n, A, B, u[N], v[N], w[N], belong[N];
inline auto solve() -> int;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i < n; i += 1)
        scanf("%d%d%d", &u[i], &v[i], &w[i]);
    scanf("%d", &A);
    for(int i = 1, x; i <= A; i += 1)
        scanf("%d", &x), belong[x] = 1;
    scanf("%d", &B);
    for(int i = 1, x; i <= B; i += 1)
        scanf("%d", &x), belong[x] = 2;
    if(A+B == n) printf("%d", solve());
    else printf("%d", Netflow::solve());
    return 0;
}
inline auto solve() -> int
{
    int ans = 0;
    for(int i = 1; i < n; i += 1)
        if(belong[u[i]] != belong[v[i]]) 
            ans += w[i];
    return ans;
}
namespace Netflow
{
    #define bl belong
    inline auto solve() -> int
    {
        Netflow::s = n+1, Netflow::t = n+2;
        for(int i = 1; i < n; i += 1)
            build(u[i], v[i], w[i]);
        for(int i = 1; i <= n; i += 1)
        {
            if(belong[i] == 1) add_edge(s, i, inf);
            if(belong[i] == 2) add_edge(i, t, inf);
        }
        while(bfs(s, t) == true)
            while((nowflow = dinic(s, INT_MAX)))
                maxflow += nowflow;
        return maxflow;
    }
    inline auto build(int u, int v, int w) -> void
    {
        if(bl[u] == 0 or bl[v] == 0 or bl[u] == bl[v]) 
            add_edge(u, v, w), add_edge(v, u, w);
        else if(bl[u] == 1) add_edge(u, v, w);
        else add_edge(v, u, w);
    }
    inline auto bfs(int s, int t) -> int
    {
        memcpy(cur, head, 4*(t+1));
        memset(vis, 0, 4*(t+1));
        queue<int> q; q.push(s);
        vis[s] = 1; int x, y;
        while(!q.empty())
        {
            x = q.front(); q.pop();
            for(int i = head[x]; i; i = a[i].next)
            {
                y = a[i].to;
                if(!vis[y] and a[i].flow)
                {
                    vis[y] = vis[x]+1;
                    if(y == t) return true;
                    q.push(y);
                }
            }
        }
        return false;
    }
    inline auto dinic(int x, int flow) -> int
    {
        if(x == t) return flow;
        int rest = flow, y, k, i;
        for(i = cur[x]; i; i = a[i].next)
        {
            y = a[i].to;
            if(vis[y] == vis[x]+1 and a[i].flow)
            {
                k = dinic(y, min(rest, a[i].flow));
                if(!k) vis[y] = 0;
                a[i].flow -= k;
                a[i^1].flow += k;
                if(!(rest -= k)) break;
            }
        }
        return cur[x] = i, flow-rest;
    }
    inline auto add_edge(int from, int to, int flow) -> void
    {
        Add_edge(from, to, flow);
        Add_edge(to, from, 0);
    }
    inline auto Add_edge(int from, int to, int flow) -> void
    {
        cnt += 1;
        a[cnt].from = from;
        a[cnt].to = to;
        a[cnt].flow = flow;
        a[cnt].next = head[from];
        head[from] = cnt;
    }
}

# PolarSea 与 IOI (contest)

# 题目描述

一场竞赛一共有 n(1≤n≤2∗103)n (1 \le n \le 2*10^3) 道题目，它们的难度组成了一个大小为 nn 的可重集 AA，其中每个元素表示一道题的难度。

对于难度为 xx 的题目，PolarSea 需要花费总共 xx 分钟才能把这道题 AC。由于 PolarSea 的比赛习惯很差，他从来不打暴力，所以如果他在难度为 xx 的题上花的时间 ≤x\le x，这道题它将得不到任何分数。

众所周知，IOI 的题目是按字典序排序的，所以 PolarSea 不知道每道题的难度，只知道它们难度的可重集是 AA。由于是 IOI 赛制，PolarSea 时刻知道每道题自己是否通过了以及在每道题上已经花的时间。

PolarSea 只有做出至少 mm 道题才能拿到 Au ，作为南极洲领队，你想知道 PolarSea 使用最优策略（不包括打暴力）下最坏要花多长时间才能拿到 Au 。

# 解题思路

由于最坏情况自己能求出来，所以实时知道自己过了哪些题只能判断当前是否不是最坏情况，那么我们不用管知道自己过了哪些题对策略的影响，就当必然是最坏情况即可。

我们把 aia_i 排序，设第 ii 道题花费了 bib_i 的时间，则 最坏情况就是 把 bib_i 也排序并一一对应。

于是问题变为：给定一个 nn 个点 (i,ai)(i,ai) 构成的右下阶梯，求一个 nn 个点 (i,bi)(i,bi) 构成的右下阶梯，使得有 mm 个 ii 满足 ai=biai=bi。

记 f(j,i)f(j,i) 表示考虑前 ii 个点，ai=biai=bi，且有 jj 个位置满足 j≤i,aj=bjj \le i,aj = bj 的最小代价。
状态转移方程记为 f(k,i)=max⁡j<i{f(k−1,j)+(i−j)∗ai}f(k,i) = \max\limits_{j < i}\{f(k-1,j)+(i-j)*a_i\}
直接转移是 O(Tn2m)O(Tn^2m)，整个斜率优化 DP (单调栈优化 DP)，就可以到 O(Tnm)O(Tnm) 的了

# Code

#define Aniciry Meteorshower_Y
#include<algorithm>
#include<iostream>
#include<climits>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 2e3+1;
int T, n, m, a[N], f[N][N];
inline auto work() -> void;
int main()
{
    scanf("%d", &T);
    while(T--) work();
    return 0;
}
inline auto X(int i, int k) -> double{return k;}
inline auto Y(int i, int k) -> double{return f[i-1][k];}
inline auto slope(int i, int j, int k) -> double{return (Y(i,j)-Y(i,k))/(X(i,j)-X(i,k));}
inline auto work() -> void
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i += 1)
        scanf("%d", &a[i]);
    sort(a+1, a+n+1, [](int a, int b){return a > b;});;
    memset(f, 0x3f, sizeof(f));f[0][0] = 0;
    for(int i = 1; i <= m; i += 1)
    {
        static int st[N], top;
        top = 1; st[top] = i-1;
        for(int j = i; j <= n; j += 1)
        {
            while(top > 1 and slope(i, st[top], st[top-1]) >= a[j]) top -= 1;
            f[i][j] = f[i-1][st[top]]+(j-st[top])*a[j];
            while(top > 1 and slope(i, st[top], st[top-1]) >= slope(i, j, st[top-1])) top -= 1;
            st[++top] = j;
        }
    }
    int ans = INT_MAX;
    for(int i = 1; i <= n; i += 1)
        ans = min(ans, f[m][i]);
    printf("%d\n", ans);
}