C. The Sports Festival

C. The Sports Festival

题意：

n个数，依次将所有数加入到区间内，每次得到一个k，k等于当前区间的最大值减最小值，
求所有k的和的最小值

题解：

一开始就没往dp那方面想，自己在dp这方面的理解还是欠缺
正解区间dp
区间[l,r]是由左右两个小区间转移得到的，分别是[l+1,r],[l,r-1]
所以不难得到：dp[l][r]=min(dp[l+1,r],dp[l,r-1])+S
S是扩大区间长度后增加的情况，增加的情况就是最大值减最小值（即a[r] - a[l]）
但是l和r不能直接从1到n枚举，因为我们说了区间[l.r]是由小区间推来的，没求出小区间怎么求大区间，所以我们循环区间长度，然后枚举左端点，右端点自然得到，这样递推式就是从小区间到大区间

代码：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b) typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=2e3+9; ll a[maxn]; ll dp[maxn][maxn]; int main() {ll n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+1+n);/*先确定区间长度，然后依次枚举左端点*/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+1][r],dp[l][r-1])+(a[r]-a[l]);}}cout<<dp[1][n];return 0; } /* dp[l][r]=min(dp[l+1][r],dp[l][r-1])+(a[r]-a[l]); */

总结

以上是生活随笔为你收集整理的C. The Sports Festival的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。