'恩 ~~这个和这个也是朋友.把他们放在一起......哇!终于完成了'mty费了好大劲,终于找出了一支最为庞大的军队.
fyc很高兴,立马出征与人fight.mty万万没想到fyc竟然把他也叫去了.偶像的命令不可违抗,mty只好跟着出发了.
两军交战采用一对一单挑的形式.mty一上来就遇到了一个对手.此人身高2米12,头大,腿粗.....这个人fight崇尚防守反击,他要等mty出手,漏出破绽才进攻,且只进攻一次.现在mty有p个招数,每招都会给对方造成伤害,也会让对手有可趁之机来攻击自己,造成伤害.
mty进攻一次需1秒,而他的对手出招很快,进攻时间可以忽略不计.
mty想在最短时间内战胜对方,请你帮帮忙.
INPUT:
第一行,三个数,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才算赢
OUTPUT:
一个数表示mty要战胜对手所需最少秒数.如果,mty不可能赢,就输出'mty zhen mei yong!'(不包括引号)
INPUT:
2 1 1
2 0
OUTPUT:
1
【参考程序】:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int n,m,a,b,k,p,i,j,ans;
int f[110][110];
bool bk;
int main()
{
scanf("%d%d%d",&n,&m,&p);
for (i=0;i<=n;i++)
for (j=0;j<=m;j++)
f[i][j]=0xfffffff;
f[0][0]=0;
for (k=1;k<=p;k++)
{
scanf("%d%d",&a,&b);
for (i=n;i>=a;i--)
for (j=m;j>=b;j--)
if (f[i-a][j-b]+1<f[i][j])
f[i][j]=f[i-a][j-b]+1;
}
ans=0xfffffff;bk=true;
for (i=0;i<=m-1;i++)
if (f[n][i]<ans)
{
ans=f[n][i];
bk=false;
}
if (bk) printf("mty zhen mei yong!\n");
else printf("%d\n",ans);
system("pause");
return 0;
}