[Offer收割]编程练习赛29 题目3 : 最大得分（DP）

时间限制: 10000ms

单点时限: 1000ms

内存限制: 256MB

描述

小Hi和小Ho在玩一个游戏。给定一个数组A=[A1, A2, ... AN]，小Hi可以指定M个不同的值S1，S2, S3 ... SM，这样他的总得分是 ΣSi × count(Si)。（count(Si)是数组中与Si相等的元素的个数)。

为了增加难度，小Ho要求小Hi选择的S1..SM其中任意两个Si和Sj都满足|Si-Sj| > 1。

你能帮助小Hi算出他最大得分是多少吗？

输入

第一行包含两个整数N和M。  

第二行包含N个整数A1, A2, ... AN。  

对于30%的数据，1 ≤ M ≤ N ≤ 10  

对于100%的数据，1 ≤ M ≤ N ≤ 1000 1 ≤ Ai ≤ 100000

输出

最大得分

样例输入

5 2  
1 2 1 2 3

样例输出

5

思路：把不同的数及其得分从A中找出进行DP。d[i][j][0]表示已经选了j个数的情况下，不选第i个数的最大得分；d[i][j][1]表示已经选了j个数的情况下，选第i个数的最大得分。

#include<bits/stdc++.h>
using namespace std;
const int MAX=2e3;
struct lenka
{
    int val,sum;
};
int A[MAX],num[1000*MAX];
int d[MAX][MAX][2];
int cmp(const lenka& x,const lenka& y){return x.val<y.val;}
vector<lenka>p;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    memset(num,0,sizeof num);
    for(int i=1;i<=n;i++)scanf("%d",&A[i]),num[A[i]]++;
    for(int i=1;i<=1000000;i++)
    {
        if(num[i]==0)continue;
        p.push_back((lenka){i,num[i]*i});
    }
    memset(d,0,sizeof d);
    sort(p.begin(),p.end(),cmp);
    int ans=0;
    for(int i=0;i<p.size();i++)
    {
        if(i==0)
        {
            d[i][1][1]=p[i].sum;
            d[i][0][0]=0;
        }
        else
        {
            for(int j=0;j<=m;j++)
            {
                if(abs(p[i].val-p[i-1].val)<=1)
                {
                    d[i][j][0]=max(d[i-1][j][0],d[i-1][j][1]);
                    if(j<m)d[i][j+1][1]=max(d[i][j+1][1],d[i-1][j][0]+p[i].sum);
                }
                else
                {
                    d[i][j][0]=max(d[i-1][j][0],d[i-1][j][1]);
                    if(j<m)d[i][j+1][1]=max(d[i-1][j][0],d[i-1][j][1])+p[i].sum;
                }
            }
        }
        for(int j=0;j<=m;j++)
        {
            ans=max(ans,d[i][j][0]);
            ans=max(ans,d[i][j][1]);
        }
    }
    cout<<ans<<endl;
    return 0;
}