Codeforces Round #598 (Div. 3)E（dp路径转移）

题：https://codeforces.com/contest/1256/problem/E

题意：给一些值，代表队员的能力值，每组要分3个或3个以上的人，然后有个评价值x=（队里最大值-最小值），问最小的∑x是多少，以及输出方案

学习粗：https://www.cnblogs.com/Lubixiaosi-Zhaocao/p/11797744.html

dp路径转移

#include<bits/stdc++.h>
using namespace std;
const int M=2e5+5;
struct node{
    int val,id;
}a[M];
int dp[M];
int ans[M],pre[M];
bool cmp(node p,node q){
    return p.val<q.val;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].val),a[i].id=i;
    sort(a+1,a+1+n,cmp);
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    pre[0]=-1;
    for(int i=3;i<=n;i++){
        for(int j=3;j<=5;j++){
            if(i-j>=0&&dp[i-j]+a[i].val-a[i-j+1].val<dp[i]){
                pre[i]=i-j;
                dp[i]=dp[i-j]+a[i].val-a[i-j+1].val;
            }
        }
    }
    int tot=0;
    for(int i=n;i>=1;i=pre[i]){
        tot++;
        for(int j=i;j>pre[i];j--)
            ans[a[j].id]=tot;
    }
    printf("%d %d\n",dp[n],tot);
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    return 0;
}

View Code