問(wèn)題 A: 勇士傳說(shuō)

內(nèi)存限制：128 MB時(shí)間限制：1 S標(biāo)準(zhǔn)輸入輸出

題目描述

勇士 haruhi 要鑄造一個(gè)傳說(shuō)!
但是在這之前，他需要打敗惡龍。
眾所周知的是，惡龍的攻擊力非常高，haruhi 作為一個(gè)攻擊力只有 0 的家伙，需要去招募青蛙來(lái)攻打惡龍。
haruhi 到惡龍巢穴的路上有 n 個(gè)酒館，每個(gè)酒館里都有一些青蛙。(不要問(wèn)青蛙為什么在酒館里)
青蛙作為一種中立生物，對(duì) haruhi 也是有敵意的，除非 haruhi 花錢招募它們，或者 haruhi 已經(jīng)招募的青蛙的攻擊力比當(dāng)前酒館里青蛙的攻擊力多或者相等，他才能安全地走出這個(gè)酒館，抵達(dá)下一個(gè)地方。
haruhi 會(huì)按照 1 到 n 的順序，走遍這些酒館。
現(xiàn)在，haruhi 想要問(wèn)你，他最少需要準(zhǔn)備多少錢，才能招募到足夠多的青蛙，打敗惡龍。
其他設(shè)定如下:
1、haruhi 只能夠選擇要么招募整個(gè)酒館的青蛙，要么一只都不要。
2、最后，青蛙的攻擊力總和大于等于惡龍，那么，haruhi 就可以順利的打敗惡龍。
3、同一個(gè)酒館里，青蛙的攻擊力是一樣的。

輸入格式

第一行一個(gè)整數(shù) T,代表 T 組數(shù)據(jù)。(T<=20)
首先每行兩個(gè)數(shù) n,k，分別代表酒館的數(shù)量，和惡龍的攻擊力。(n<=500,k<=10^9)
接下來(lái)有三行。
第一行 n 個(gè)數(shù)，代表每個(gè)酒館里青蛙的數(shù)量。(1<=a[i]<=3000)
第二行 n 個(gè)數(shù)，代表每個(gè)酒館里每只青蛙的攻擊力。(1<=b[i]<=3000)
第三行 n 個(gè)數(shù)，代表招募到這個(gè)酒館所有青蛙所需要付出的金幣數(shù)。(1<=c[i]<=10)

輸出格式

對(duì)于每組數(shù)據(jù)，輸出一個(gè)數(shù)，代表 haruhi 需要花的最少錢數(shù)。
如果 haruhi 戰(zhàn)勝不了惡龍，輸出"chu ti zhe ying gai xue yi xia e long"。(不含引號(hào))

輸入樣例 復(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;
}