首页 > ACM题库 > HDU-杭电 > HDU 3008-Warcraft-动态规划-[解题报告]HOJ
2014
02-27

HDU 3008-Warcraft-动态规划-[解题报告]HOJ

Warcraft

问题描述 :

Have you ever played the Warcraft?It doesn’t matter whether you have played it !We will give you such an experience.There are so many Heroes in it,but you could only choose one of them.Each Hero has his own skills.When such a Skill is used ,it costs some MagicValue,but hurts the Boss at the same time.Using the skills needs intellegence,one should hurt the enemy to the most when using certain MagicValue.

Now we send you to complete such a duty to kill the Boss(So cool~~).To simplify the problem:you can assume the LifeValue of the monster is 100, your LifeValue is 100,but you have also a 100 MagicValue!You can choose to use the ordinary Attack(which doesn’t cost MagicValue),or a certain skill(in condition that you own this skill and the MagicValue you have at that time is no less than the skill costs),there is no free lunch so that you should pay certain MagicValue after you use one skill!But we are good enough to offer you a "ResumingCirclet"(with which you can resume the MagicValue each seconds),But you can’t own more than 100 MagicValue and resuming MagicValue is always after you attack.The Boss is cruel , be careful!

输入:

There are several test cases,intergers n ,t and q (0<n<=100,1<=t<=5,q>0) in the first line which mean you own n kinds of skills ,and the "ResumingCirclet" helps you resume t points of MagicValue per second and q is of course the hurt points of LifeValue the Boss attack you each time(we assume when fighting in a second the attack you show is before the Boss).Then n lines follow,each has 2 intergers ai and bi(0<ai,bi<=100).which means using i skill costs you ai MagicValue and costs the Boss bi LifeValue.The last case is n=t=q=0.

输出:

There are several test cases,intergers n ,t and q (0<n<=100,1<=t<=5,q>0) in the first line which mean you own n kinds of skills ,and the "ResumingCirclet" helps you resume t points of MagicValue per second and q is of course the hurt points of LifeValue the Boss attack you each time(we assume when fighting in a second the attack you show is before the Boss).Then n lines follow,each has 2 intergers ai and bi(0<ai,bi<=100).which means using i skill costs you ai MagicValue and costs the Boss bi LifeValue.The last case is n=t=q=0.

样例输入:

4 2 25
10 5
20 10
30 28
76 70
4 2 25
10 5
20 10
30 28
77 70
0 0 0

样例输出:

4
My god

Hint
Hint: When fighting,you can only choose one kind of skill or just to use the ordinary attack in the whole second,the ordinary attack costs the Boss 1 points of LifeValue,the Boss can only use ordinary attack which costs a whole second at a time.Good Luck To You!

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3008

分析:用dp[i][j]表示攻击了i次对其造成j点伤害自身剩余,则有

           dp[i][j+b[k]] = max( dp[i][j+b[k]],
dp[i-1][j]-a[i]
);

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iomanip>
using namespace std;

int dp[105][105];///dp[i][j]表示攻击了i次,打了对方j点生命,自己剩下的魔值
int a[105]= {0};
int b[105]= {1};

int main() {
    int n,t,k;
    while(cin>>n>>t>>k,n+t+k) {
        int m=100/k+(100%k?1:0);
        for(int i=1; i<=n; ++i)
            cin>>a[i]>>b[i];
        memset(dp,-1,sizeof(dp));
        dp[0][0]=100;///开始时魔法值为100
        for(int i=1;i<=m;++i)
            for(int j=0;j<=100;++j)
                if(dp[i-1][j]!=-1){
                    dp[i-1][j] = (dp[i-1][j]+t)>100 ? 100:dp[i-1][j]+t;///魔值不超过100
                    for(int k=0;k<=n;++k)
                        if(dp[i-1][j]>=a[k]&&dp[i-1][j]-a[k]>dp[i][j+b[k]])
                            if(j+b[k]>=100)
                                dp[i][100]=dp[i-1][j]-a[k];
                            else
                                dp[i][j+b[k]]=dp[i-1][j]-a[k];
                }
        int p=1;
        for( ;p<=m;++p)
        if(dp[p][100]!=-1){
            cout<<p<<endl; break;
        }
        if(p>m)puts("My god");
    }
    return 0;
}

参考:http://blog.csdn.net/du489380262/article/details/8936886


  1. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count

  2. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts

  3. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。