hdu 3008 Warcraft (dp)

思路分析：

dp[i][j] 第i秒  有j点魔法   可以消耗boss的最大生命值

可以将普通攻击看成伤害为1  耗蓝为0 的一个技能

c 为耗蓝   v为伤害

枚举上一秒的每一个状态

int tag=k-c[j]+t;
if(tag>100)tag=100;
dp[i][tag]=max(dp[i][tag],dp[i-1][k]+v[j]);

卡了好久

如果q=25  那么他可以坚持到第四秒

如果q=23 那么他可以坚持到第五秒。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n,t,q;
int v[105];
int c[105];
int dp[105][105];

int main()
{
    while(scanf("%d%d%d",&n,&t,&q)!=EOF)
    {
        if(!n && !t && !q)break;
        for(int i=1;i<=n;i++)
        scanf("%d%d",&c[i],&v[i]);
        
        c[0]=0;v[0]=1;

        memset(dp,0,sizeof dp);

        for(int i=0;i<=n;i++)
        {
            if(c[i]<=100)
            {
                int tag=100-c[i]+t;
                if(tag>100)tag=100;
                dp[1][tag]=max(dp[1][tag],v[i]);
            }
        }

        for(int i=2;i<=100;i++)
        {
            for(int j=0;j<=n;j++)
            {
                for(int k=c[j];k<=100;k++)
                {
                    if(dp[i-1][k])
                    {
                        int tag=k-c[j]+t;
                        if(tag>100)tag=100;

                        dp[i][tag]=max(dp[i][tag],dp[i-1][k]+v[j]);
                    }
                }
            }
        }
        int lit=100/q;
        if(100%q!=0)lit++;
        int Min=0x3f3f3f3f;
        for(int i=1;i<=lit;i++)
        {
            for(int j=0;j<=100;j++)
            if(dp[i][j]>=100)Min=min(i,Min);
        }
        if(Min!=0x3f3f3f3f)printf("%d\n",Min);
        else printf("My god\n");
    }
    return 0;
}

hdu 3008 Warcraft (dp)

原文：http://blog.csdn.net/u010709592/article/details/18867497