Codeforces地址
C. The Sports Festival(区间DP)
题目要求我们给出重新排列出发顺序后\(\sum\limits_{i=1}^{n}d_i\)的最小值，如果我们使用暴力计算的话，由于\(n\)的范围较大，一定会超时。但是我们可以使用动态规划的方式来计算。我们先来考虑最后一个人出发时候的差值是多少，并且如何能够使得这个差值在最后阶段之前更小。容易想到的是，我们让队列中速度最慢的或者最快的人最后出发就可以。因此我们可以先将队列按照跑步速度来排列，这里花费\(O(nlogn)\)的时间。
紧接着，我们可以继续使用先前的结论，对于队列中的子队列\(l\sim r\)，计算子队列中的最小差值的和，因此我们可以得到\(dp\)转移方程\(dp[l][r]=min(dp[l+1,r],dp[l,r-1])+rate[r]-rate[l]\)。由于我们计算当前序列的时候，我们需要用到此前子序列的结果，因此我们就枚举区间长度，先把子区间的结果计算出来。最后得到的算法时间复杂度为\(O(n^2)\)
动态规划
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;
vector<int> rate(n);
vector<vector<LL>> dp(n,vector<LL>(n));
for(int i=0;i<n;i++)
{
cin>>rate[i];
dp[i][i]=0;//长度为1的时候差值为0
}
sort(rate.begin(),rate.end());
for(int len=2;len<=n;len++)//区间dp枚举区间长度
{
for(int l=0;l+len-1<n;l++)
{
int r=l+len-1;
dp[l][r]=rate[r]-rate[l]+min(dp[l+1][r],dp[l][r-1]);
}
}
cout<<dp[0][n-1];
return 0;
}
当然，我们可以将区间\(dp\)的算法写成记忆化搜索的形式，相比起\(dp\)的方式会更容易写一些。
记忆化搜索
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
typedef long long LL;
LL f[N][N];
int rate[N];
LL dfs(int l,int r)
{
if(f[l][r]!=-1)//如果计算过就直接返回对应的值
return f[l][r];
if(l==r)//说明只有一个人，区间长度为1
return 0;
return f[l][r]=rate[r]-rate[l]+min(dfs(l+1,r),dfs(l,r-1));
}
int main()
{
int n;
cin>>n;
memset(f,-1,sizeof f);
for(int i=0;i<n;i++) cin>>rate[i];
sort(rate,rate+n);
cout<<dfs(0,n-1);
return 0;
}