Description

Solution

可以把题目转化一下模型，将间隔取出来，转化为N-1个数，限制不能取相邻两个数，求取K个数的最小价值

设DP[i][j]表示前i个数取j个最大价值（第i个数取），那么DP[i][j]=min{DP[i-1][j],DP[i-2][j-1]+d[i]}

但是，这样显然是会超时的，

考虑一个性质，在最优方案中，取的数一定是在所有数中最小的3*K个数中，最坏的情况下最小的3*K个数全部连在一起方案也在这里面

那么就可以吧O(nk)优化为O(k²)

最后滚动数组优化一下空间就好了

Code

 

#include 
     
      #include 
      
       #include 
       
        #define fst first#define sed second#define N 500010using namespace std;int n,k,dp[4][5010],t[N],d[N],p;pair
        
          A[N];bool b[N];inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}int main(){	k=read(),n=read();	for(int i=1;i<=n;++i) t[i]=read();	sort(t+1,t+n+1);	for(int i=1;i