問題 A: 勇士傳說
問題 A: 勇士傳說
內(nèi)存限制：128 MB時間限制：1 S標(biāo)準(zhǔn)輸入輸出
題目描述
勇士 haruhi 要鑄造一個傳說!
但是在這之前，他需要打敗惡龍。
眾所周知的是，惡龍的攻擊力非常高，haruhi 作為一個攻擊力只有 0 的家伙，需要去招募青蛙來攻打惡龍。
haruhi 到惡龍巢穴的路上有 n 個酒館，每個酒館里都有一些青蛙。(不要問青蛙為什么在酒館里)
青蛙作為一種中立生物，對 haruhi 也是有敵意的，除非 haruhi 花錢招募它們，或者 haruhi 已經(jīng)招募的青蛙的攻擊力比當(dāng)前酒館里青蛙的攻擊力多或者相等，他才能安全地走出這個酒館，抵達(dá)下一個地方。
haruhi 會按照 1 到 n 的順序，走遍這些酒館。
現(xiàn)在，haruhi 想要問你，他最少需要準(zhǔn)備多少錢，才能招募到足夠多的青蛙，打敗惡龍。
其他設(shè)定如下:
1、haruhi 只能夠選擇要么招募整個酒館的青蛙，要么一只都不要。
2、最后，青蛙的攻擊力總和大于等于惡龍，那么，haruhi 就可以順利的打敗惡龍。
3、同一個酒館里，青蛙的攻擊力是一樣的。
輸入格式
第一行一個整數(shù) T,代表 T 組數(shù)據(jù)。(T<=20)
首先每行兩個數(shù) n,k，分別代表酒館的數(shù)量，和惡龍的攻擊力。(n<=500,k<=10^9)
接下來有三行。
第一行 n 個數(shù)，代表每個酒館里青蛙的數(shù)量。(1<=a[i]<=3000)
第二行 n 個數(shù)，代表每個酒館里每只青蛙的攻擊力。(1<=b[i]<=3000)
第三行 n 個數(shù)，代表招募到這個酒館所有青蛙所需要付出的金幣數(shù)。(1<=c[i]<=10)
輸出格式
對于每組數(shù)據(jù)，輸出一個數(shù)，代表 haruhi 需要花的最少錢數(shù)。
如果 haruhi 戰(zhàn)勝不了惡龍，輸出"chu ti zhe ying gai xue yi xia e long"。(不含引號)
輸入樣例 復(fù)制
1
3 9
2 2 3
3 4 1
5 8 1
輸出樣例 復(fù)制
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;
}