hdoj 4976 A simple greedy problem.【dp】

àì夳堔傛蜴生んèń 2022-08-11 08:00 145阅读 0赞

题目：[hdoj 4976 A simple greedy problem.][]

来源：[2014 Multi-University Training Contest 10][]

分类：dp or greedy

题意：有两个人A和B,还有一堆血量已知的怪，然后A每次可以给一个怪 1 的伤害，B每次给所有 1 的伤害，每次由A先来，轮流，问A最多能杀死多少怪。

分析：这个题目当时比赛的时候想到的是贪心的策略，每次选定一个A最小的奇数，如果没有奇数，那么选定一个大于二的最小的偶数，然后其他的让B操作，写的时候差不多O（n^2）的复杂度，超时了。但是至今感觉这个策略是对的。求解。。。

dp的话首先也是一个贪心的策略，如果我们要保证A杀死最多的怪，那么我们让所有怪的血量都都不同，比如样例1,2,3,4,5.A杀死1，然后B让所有-1，然后A又可以杀死最前面一个，这样的话所有的都能让A杀死，这样，我们就可以通过让A杀几次的代价处理让所有的怪的血量都不同，预处理。

然后定义状态转移方程：dp【i】【j】 ：B攻击了 i 次，而 A 预留了 j 次攻击的 A 最大的杀敌数量。

然后状态转移：dp【i】【j】 = max（dp【i-1】【j-1】，dp【i-1】【j+cost【i】】+1）,即当前这一轮没有杀死，或者杀死了一个。

AC代码：

#include <cstdlib>
    #include <cctype>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <string>
    #include <iostream>
    #include <sstream>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <fstream>
    #include <numeric>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stdexcept>
    #include <functional>
    #include <utility>
    #include <ctime>
    using namespace std;
    const int N = 1100;
    int a[N],cost[N];
    int dp[N][N];
    int main()
    {
        int T;
        scanf("%d",&T);
        for(int cas=1;cas<=T;cas++)
        {
            int n;
            scanf("%d",&n);
            int ma = 0;
            for(int i=0;i<n;i++){
                scanf("%d",&a[i]);
                ma = max(ma,a[i]);
            }
            sort(a,a+n);
            memset(cost,0,sizeof(cost));
            memset(dp,-1,sizeof(dp));
            for(int i=0;i<n;i++)  //预处理
            {
                int val = 1,tmp = a[i];
                while(cost[tmp] && tmp>=1)
                {
                    val++;
                    tmp--;
                }
                if(tmp>0)
                    cost[tmp]=val;
            }
            dp[0][0] = 0;
            for(int i=1;i<=ma;i++)  //dp
            {
                for(int j=0;j<=i;j++)
                {
                    if ( j - 1 >= 0)
                        dp[i][j] = max(dp[i][j], dp[i - 1][j - 1]);
                    if (cost[i] && j + cost[i] - 1 <= i )
                        dp[i][j] = max(dp[i][j], dp[i - 1][j + cost[i] - 1]+1);
                }
            }
            int ans=0;
            for(int i=0;i<=ma;i++)
                ans=max(ans,dp[ma][i]);
            printf("Case #%d: %d\n",cas,ans);
        }
        return 0;
    }

[hdoj 4976 A simple greedy problem.]: http://acm.hdu.edu.cn/showproblem.php?pid=4976
[2014 Multi-University Training Contest 10]: http://acm.hdu.edu.cn/search.php?field=problem&key=2014%20Multi-University%20Training%20Contest%2010&source=1&searchmode=source