Klee likes making friends

题目大意

总共n个人，从任意m个人里选两个人，求所需的最小价值。

解题思路

一眼看过去很像单调队列优化dp的典题，然后用单调队列做了半天，发现单调队列存储的信息太少了，做不了这个题。然后就想到了用后缀数组。
$dp[i][j]$表示倒数第一个朋友是$i$，倒数第二个朋友是$j$，那么很容易得出倒数第三个朋友所属的区间为$[i-m,j-1]$，拿后缀最小值数组记录一下即可。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define maxm 20010
#define maxn 2010
typedef __int128_t int128;
using namespace std;
const int inf=1e9;
int w[maxm],dp[maxn][maxn];   //dp[i][j]表示到第i位且i,j是朋友的合法情况下的最小答案
int g[maxn][maxn];   //g[i][j]表示第i位且i,j是朋友,倒数第二个朋友从i-1到j的最小值
void solve(){
    int n,m,ans=inf;
    cin >> n >> m;
    for(int i=1;i<=n;++i)  cin >> w[i];
    for(int i=1;i<=m;i++){     //初始化
        for(int j=0;j<=m;j++)  dp[i][j]=g[i][j]=inf;
        for(int j=i-1;j>=1;--j){   //倒着求后缀最小值
            dp[i][j]=w[i]+w[j];
            g[i][j]=min(g[i][j+1],dp[i][j]);
        }
    }
    for(int i=m+1;i<=n;++i){
        for(int j=i-1;j>=i-m+1;--j){
            int u=(i-1)%m+1,v=(j-1)%m+1;
            dp[u][v]=g[v][u]+w[i];      //在取模后会惊奇的发现，i和i-m是一个值，然后代码就很好看^_^
            g[u][v]=min(g[u][j%m+1],dp[u][v]);
        }
    }
    for(int i=n-m+1;i<=n;++i){
        for(int j=n-m+1;j<i;++j){
            ans=min(ans,dp[(i-1)%m+1][(j-1)%m+1]);
        }
    }
    cout << ans << '\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;  cin >> t;
    while(t--){
        solve();
    }
    return 0;
}