C. The Sports Festival
题意:
给定一个序列a[]。
定义\(d_i=max(a_1,a_2,…,a_i)−min(a_1,a_2,…,a_i)\)
求解最小的\(\sum d_i\)
解析:
不妨从后往前思考\(d[i]\)的值是确定的,那么可以减少\(d[i-1]\)的方法,只有可能是减少最大值或者最小值。也就是说d[i]是从这两个状态转换过来的。
不妨考虑DP(开始想的贪心,贪了一个小时没写出来,贪心的思路应该是错误的)。
定义:dp[l][r]是从l到r的d值。
之前已经得到了转移的思路,现在开始实现它,因为我们每一次取走的都是最大值或者最小值。我们不妨先排序。
这样就变成了:
\(dp[l][r] = min(dp[l+1][r]-a[l]+a[l+1,dp[l][r-1]-a[r-1]+a[r])\)
显然这是一个区间DP问题。
代码实现就是区间DP。
下面用递推的实现(万总似乎因为写的递归被卡了)
1. int n;
2. ll dp[N][N];
3. int a[N];
4. int main() {
5. ios::sync_with_stdio(false);
6. cout.tie(NULL);
7. cin>>n;
8. for(int i = 1;i <= n;i++) cin>>a[i];
9. sort(a+1,a+n+1);
10. for(int l = 1;l <= n;l++){
11. for(int i = 1;i <= n-l;i++){
11. int j = i+l;
12. dp[i][j] = min(dp[i+1][j],dp[i][j-1])+a[j]-a[i];
13. }
14. }
15. cout<<dp[1][n]<<endl;
16. return 0;
17. }