NamoCamp 每日一題 體育節 區間DP

​​|–>題目傳送門<–|​​

題目描述

學生會正在為體育節的接力賽做準備。學生會由 n個成員組成，他們将在比賽中一個一個地跑，第 個人的速度是 ，第 i次接力會産生一個差異值 ，它的值是前 個參與接力賽的人的速度最大值與最小值的差，也就是說，我們假設第個參與比賽的人的速度是 ，那麼 。現在你可以任意安排參加比賽的人的順序，一個人隻能參與一次，且每個人都必須參與，請你求出的最小值。

題解

首先考慮插入數字的影響：

• 如果是區間，那麼新增
• 如果是區間，那麼新增
• 如果都不是，那麼新增

那麼顯然，每插入一個區間最大值，新增極差的大小都會，從貪心的角度考慮，我們應當盡可能晚的插入區間最大值。是以我們可以先對所有的排序。

設表示區間的答案(和的最小值)。

考慮一段區間的狀态：顯然可以由(表示的貢獻)：

#include <bits/stdc++.h>
#define int long long


const int N = 2e3 + 10;
int a[N], dp[N][N];

inline bool cmp(const int &a, const int &b){ return a < b; }

inline void solve(){
  int n = 0; std::cin >> n;
  for(register int i = 1; i <= n; i++) std::cin >> a[i];
  std::sort(a + 1, a + 1 + n, cmp);
  for(int len = 2; len <= n; len++){
    for(int l = 1; l <= n; l++){
      int r = l + len - 1;
      if(r > n) continue;
      dp[l][r] = (a[r] - a[l]) + std::min(dp[l + 1][r], dp[l][r - 1]); 
    }
  }
  std::cout << dp[1][n] << std::endl;
}

signed main(){
  solve();
  return 0;
}