A simple greedy problem（hdu 4976）

题意：有n个小兵，每个小兵有a【i】血量，第一个人每次只能对一个小兵砍一滴血，第二个人每次对所有生存的小兵砍一滴血。

　　　最后看第一个人最多可以砍杀几个小兵。

/*

    首先，如果所有小兵的血量都不同的话，我们可以杀死所有的小兵，如果所以我们应该尽量使小兵血量不同，

    也就是在不能将某个小兵一击致命的情况下，对某个某个血量相同的小兵砍一刀，使其血量不同。

    预处理出c[i]表示i血量这个位置上的小兵是由c[i]血量的小兵砍过来的。

    dp[i][j]表示进行了i轮之后，留有的砍兵机会为j次的最大值。

    dp[i][j]=max(dp[i-1][j-1],dp[i-1][j+c[i]-i])

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 1010

using namespace std;

int c[N],d[N],dp[N][N],s[N],n,m,top,cas;

int main(){

    int T;scanf("%d",&T);

    while(T--){

        m=,top=;

        memset(d,,sizeof(d));

        memset(c,,sizeof(c));

        memset(dp,,sizeof(dp));

        scanf("%d",&n);

        for(int i=;i<=n;i++){

            int x;scanf("%d",&x);

            d[x]++;m=max(m,x);

        }

        for(int i=;i<=m;i++){

            if(d[i]==) c[i]=i;

            else if(d[i]==) s[++top]=i;

            else {

                c[i]=i;

                while(top&&d[i]>){

                    int x=s[top];

                    if(i-x<=top){

                        top--;

                        c[x]=i;

                        d[i]--;

                    }

                    else break;

                }

            }

        }

        for(int i=;i<=m;i++)

            for(int j=;j<=i;j++){

                if(j) dp[i][j]=dp[i-][j-];

                if(c[i]&&j+c[i]-i<i) dp[i][j]=max(dp[i][j],dp[i-][j+c[i]-i]+);

            }

        int ans=;

        for(int i=;i<=m;i++)

            ans=max(ans,dp[m][i]);

        printf("Case #%d: %d\n",++cas,ans);

    }

    return ;

}