本文共 699 字，大约阅读时间需要 2 分钟。

B 

        给一个数列，任意安排顺序，让所有下标距离为k的两个元素作差，取绝对值，全部加起来，问和最小是多少。

        分析一下就能知道，根据下标取模得数的不同，可以把这些数分为k组。在最优解情况下，每一组可以让里面的数单调，并且不同组之间也单调，然后就是dp了。比赛的时候想了好久没想清楚怎么dp，功力尚浅啊。。因为我总想着用元素的下标表示状态。。。其实，k组数里面，有n%k个大组，k-(n%k)个小组，大组比小组多一个数，组数最多为5000。只需要用大组和小组各有多少个来表示状态即可。解题难点在于巧妙表示状态！

#include
   
    using namespace std;#define ll long longconst ll INF = 1000000000000000LL;int a[300010];ll dp[5010][5010];int main(){    int n,k;    cin>>n>>k;    for(int i=0;i
    
     0)dp[j][i-j]=min(dp[j][i-j],dp[j-1][i-j]+a[pos]-a[pos-gsize+1]);            if(i-j>0)dp[j][i-j]=min(dp[j][i-j],dp[j][i-j-1]+a[pos]-a[pos-gsize]);            if(i==k&&s==j){                ans=min(ans,dp[j][k-j]);            }        }    }    cout<
     
      <
     
    
   

转载地址：https://blog.csdn.net/squee_spoon/article/details/47961529 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！