C. The Sports Festival
题意：
给定一个长度为n的序列，构造一个序列使得∑i=1ndi最小。
其中d i = m a x ( a 1 , a 2 … … a i ) − m i n ( a 1 , a 2 … … a i )
思路：
以为是构造就溜了，感谢KingZhang带
正解是排序后区间dp。
考虑每次区间[ l , r ]的扩张对答案的贡献，由于已经排序过了，所以贡献是a [ r ] − a [ l ]为扩张后区间的最大值，a [ l ]为扩张后区间的最小值。
d p [ l ] [ r ]表示区间扩张到[ l , r ]时的答案的最小值。
转移有两个方向：
[ l + 1 , r ]到[ l , r ]和[ l , r − 1 ]到[ l , r ]每次转移的代价为a [ r ] − a [ l ]
时间复杂度O ( n 2 )
希望不会fst掉
代码：
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read() { ll x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b, ll p) { ll res = 1; while(b) { if(b & 1)res = res * a % p; a = a * a % p; b >>= 1; } return res; } const int inf = 0x3f3f3f3f; #define PI acos(-1) const double eps = 1e-8; const int maxn =1e5+7; ll n,a[2100],dp[2100][2100]; int main(){ n=read; for(int i=1;i<=n;i++) a[i]=read; sort(a+1,a+1+n); // memset(dp,0x3f,sizeof dp); // for(int i=1;i<=n;i++) dp[i][i]=0; for(int len=2;len<=n;len++){ for(int l=1;l+len-1<=n;l++){ int r=l+len-1; dp[l][r]=min(dp[l][r-1],dp[l+1][r])+(a[r]-a[l]); } } cout<<dp[1][n]<<endl; return 0; }
