问题 A: 勇士传说
问题 A: 勇士传说
内存限制：128 MB时间限制：1 S标准输入输出
题目描述
勇士 haruhi 要铸造一个传说!
但是在这之前，他需要打败恶龙。
众所周知的是，恶龙的攻击力非常高，haruhi 作为一个攻击力只有 0 的家伙，需要去招募青蛙来攻打恶龙。
haruhi 到恶龙巢穴的路上有 n 个酒馆，每个酒馆里都有一些青蛙。(不要问青蛙为什么在酒馆里)
青蛙作为一种中立生物，对 haruhi 也是有敌意的，除非 haruhi 花钱招募它们，或者 haruhi 已经招募的青蛙的攻击力比当前酒馆里青蛙的攻击力多或者相等，他才能安全地走出这个酒馆，抵达下一个地方。
haruhi 会按照 1 到 n 的顺序，走遍这些酒馆。
现在，haruhi 想要问你，他最少需要准备多少钱，才能招募到足够多的青蛙，打败恶龙。
其他设定如下:
1、haruhi 只能够选择要么招募整个酒馆的青蛙，要么一只都不要。
2、最后，青蛙的攻击力总和大于等于恶龙，那么，haruhi 就可以顺利的打败恶龙。
3、同一个酒馆里，青蛙的攻击力是一样的。
输入格式
第一行一个整数 T,代表 T 组数据。(T<=20)
首先每行两个数 n,k，分别代表酒馆的数量，和恶龙的攻击力。(n<=500,k<=10^9)
接下来有三行。
第一行 n 个数，代表每个酒馆里青蛙的数量。(1<=a[i]<=3000)
第二行 n 个数，代表每个酒馆里每只青蛙的攻击力。(1<=b[i]<=3000)
第三行 n 个数，代表招募到这个酒馆所有青蛙所需要付出的金币数。(1<=c[i]<=10)
输出格式
对于每组数据，输出一个数，代表 haruhi 需要花的最少钱数。
如果 haruhi 战胜不了恶龙，输出"chu ti zhe ying gai xue yi xia e long"。(不含引号)
输入样例 复制
1
3 9
2 2 3
3 4 1
5 8 1
输出样例 复制
13
代码：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int a[3005];
int b[3005];
int c[3005];
int dp[505][5015][2];
int main()
{
int n,k;
int T;
cin>>T;
while(T--)
{
cin>>n>>k;
for(int i=1; i<=n; i++ )
cin>>a[i];
for(int i=1; i<=n; i++ )
cin>>b[i];
for(int i=1; i<=n; i++ )
cin>>c[i];
memset(dp,-1,sizeof dp);
dp[0][0][0] = 0;
for(int i=0; i<=n; i++ )
{
for(int j=0; j<=5000; j++ )
{
if( dp[i][j][0] != -1 )
{
dp[i+1][j+c[i+1]][1] = max( dp[i+1][j+c[i+1]][1], dp[i][j][0]+a[i+1]*b[i+1] );
if( dp[i][j][0] >= a[i+1]*b[i+1] )
dp[i+1][j][0] = max(dp[i+1][j][0] , dp[i][j][0] );
}
if( dp[i][j][1] != -1 )
{
dp[i+1][j+c[i+1]][1] = max(dp[i+1][j+c[i+1]][1], dp[i][j][1]+a[i+1]*b[i+1] );
if( dp[i][j][1] >= a[i+1]*b[i+1] )
dp[i+1][j][0] = max(dp[i+1][j][0] , dp[i][j][1] );
}
}
}
bool flag = true;
for(int m=0; m<=5000; m++)
{
if( dp[n][m][0] >=k || dp[n][m][1] >= k )
{
cout<<m<<endl;
flag = false;
break;
}
}
if(flag)
cout<<"chu ti zhe ying gai xue yi xia e long"<<endl;
}
return 0;
}
评论