题目链接:https://codeforces.ml/contest/571/problem/B
题目大意:
给一段序列a_i,你可以对其重排,要求重排之后的:
最大
题目思路:
首先裂项相消:
a[i+k]-a[i]
a[i+2*k] - a[i+k]
sum = a[i+x*k]-a[i]
性质1:也就是这个每个数相距为k的子序列的权值实际即为a[i+x*k]-a[i]
性质2:
可以发现有长度为n%k个 n/k+1的子序列
有k-n%k个 n/k的子序列
因为要求重排,所以直接排序后,题目就转换为:
选出n%k段连续区间长度为n/k+1的区间 和 k-n%k个区间长度为n/k的区间,使得每段区间的最大值减最小值的和最小
所以令dp[i][k] 选了i段n/k+1的区间,k段n/k的区间
所以转移方程:
令aim = i*(x+1) + k*x ,x = n/k
这种dp的状态转移方程并不常见,正确性是因为选了i段与k段可以把当前选择了多少个数给确定出来
这和之前牛客多校有一个状态转移非常的相似,不得不说还是要留心这种转移
Code:
/*** keep hungry and calm CoolGuang!***/
#include
#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include
#include
#include
#include
#include
#define debug(x) cout<<#x<<":"<using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF&#61;2e18;
const int maxn&#61;1e6&#43;6;
const int mod&#61;1e9&#43;7;
const double eps&#61;1e-15;
inline bool read(ll &num)
{char in;bool IsN&#61;false;in&#61;getchar();if(in&#61;&#61;EOF) return false;while(in!&#61;&#39;-&#39;&&(in<&#39;0&#39;||in>&#39;9&#39;)) in&#61;getchar();if(in&#61;&#61;&#39;-&#39;){ IsN&#61;true;num&#61;0;}else num&#61;in-&#39;0&#39;;while(in&#61;getchar(),in>&#61;&#39;0&#39;&&in<&#61;&#39;9&#39;){num*&#61;10,num&#43;&#61;in-&#39;0&#39;;}if(IsN) num&#61;-num;return true;}
ll n,m,p;
ll dp[5005][5005];
ll num[maxn];
int main()
{read(n);read(m);ll x &#61; n/m;ll len1 &#61; n%m;///x&#43;1ll len2 &#61; m-n%m;///xfor(int i&#61;1;i<&#61;n;i&#43;&#43;) read(num[i]);sort(num&#43;1,num&#43;1&#43;n);for(int i&#61;0;i<&#61;len1;i&#43;&#43;){for(int k&#61;0;k<&#61;len2;k&#43;&#43;){if(!i&&!k){dp[i][k] &#61; 0;continue;}dp[i][k] &#61; INF;int aim &#61; i*(x&#43;1)&#43;k*x;if(i) dp[i][k] &#61;min(dp[i][k],dp[i-1][k]&#43;num[aim]-num[aim-x]);if(k) dp[i][k] &#61;min(dp[i][k],dp[i][k-1]&#43;num[aim]-num[aim-x&#43;1]);}}printf("%lld\n",dp[len1][len2]);return 0;
}
/**
5 2 2
1 5
1 2
2 3
3 4
4 5
**/