RQNOJ 356 mty的格斗 dp

PID356 / mty的格斗

题目描述

’恩 ~~这个和这个也是朋友.把他们放在一起......哇!终于完成了’mty费了好大劲,终于找出了一支最为庞大的军队.

fyc很高兴,立马出征与人fight.mty万万没想到fyc竟然把他也叫去了.偶像的命令不可违抗,mty只好跟着出发了.

两军交战采用一对一单挑的形式.mty一上来就遇到了一个对手.此人身高2米12,头大,腿粗.....这个人fight崇尚防守反击,他要等mty出手,漏出破绽才进攻,且只进攻一次.现在mty有p个招数,每招都会给对方造成伤害,也会让对手有可趁之机来攻击自己,造成伤害.

mty进攻一次需1秒,而他的对手出招很快,进攻时间可以忽略不计.

mty想在最短时间内战胜对方,请你帮帮忙.

输入格式

第一行,三个数,n,m,p(对方有n点HP,mty有m点,mty有p个招数)； n<=100,m<=100,p<=1000；

接下来p行,每行两个数,x[i],y[i](表示这招会给对方造成x[i]点伤害,对手会给mty造成y[i]点伤害)；

只有当对方HP为0,不包括负数,mtyHP为正数时,mty才算赢

输出格式

一个数表示mty要战胜对手所需最少秒数.如果,mty不可能赢,就输出’mty zhen mei yong!’(不包括引号)

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define mod 1000000007

#define esp 0.00000000001

const int N=1e3+,M=1e6+,inf=1e9;

int dp[N][N];

int a[N],b[N];

int main()

{

    int x,y,z,i,t;

    while(~scanf("%d%d%d",&x,&y,&z))

    {

        for(i=;i<=x;i++)

        for(t=;t<=y;t++)

        dp[i][t]=inf;

        for(i=;i<z;i++)

        scanf("%d%d",&a[i],&b[i]);

        dp[x][y]=;

        for(int j=;j<z;j++)

        {

            for(i=;i<=x-a[j];i++)

            {

                for(t=;t<=y-b[j];t++)

                dp[i][t]=min(dp[i+a[j]][t+b[j]]+,dp[i][t]);

            }

        }

        int ans=inf;

        for(i=;i<=y;i++)

        ans=min(ans,dp[][i]);

        if(ans==inf)

        printf("mty zhen mei yong!\n");

        else

        printf("%d\n",ans);

    }

    return ;

}

/*

dp[i][t]=min(dp[i+a[j]][t+b[j]]+1,dp[i][t]);

dp[i][t]表示最小的使用秒数；

i表示对方的HP；t表示mty的HP；

*/

巴特西

RQNOJ 356 mty的格斗 dp

最新文章

热门文章