杂题——勇士传说

题目描述

勇士 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
13 92 2 33 4 15 8 1

样例输出

13

思路

​ 一个经典的dp问题,和一般dp问题的区别就一个:多了个限制你是否可以选择不选的条件,就是你的战斗力要足够高.其他和一般的线性DP问题是一样的……

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
// #define max(a, b) ((a) > (b) ? (a) : (b))
// #define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;


const int INF = 1e9;
const int N = 510, M = 5e3 + 10;
int a[N], b[N], c[N];
LL ans = INF;
int n, k;


// 表示对于前i个酒楼,金币 = j的,k为0表示第i个楼内的蛙招募,k为1不招募.的时候的最大战斗力
int dp[N][M][2];

void solve() {
    memset(dp, -1, sizeof dp);
    int n, k;
    cin>> n >> k;
    
    fore (i, 1, n) cin >> a[i];
    fore (i, 1, n) cin >> b[i];
    fore (i, 1, n) cin >> c[i];
    
    dp[0][0][0] = 0;
    fore (i, 0, n){
        fore (j, 0, 5010){
            // 表示可以到达这个状态
            if(dp[i][j][0] != -1){
                // 表示前i + 1个楼,金币 为j + c[i + 1]的情况就只有两种,一种就是
                // 之前前i个楼的金币已经达到了的,还有一种就是之前金币还没到,现在加上
                // c[i + 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]);
                }
            }
        }
    }
    
    // 下面就是我们查看战斗力第一次大于k的时候就是我们最少需要花费的金币
    bool flag = true;
    fore (i, 0, 5000){
        if(dp[n][i][0] >= k || dp[n][i][1] >= k){
            cout << i << ed;
            flag = false;
            break;
        }
    }
    
    if(flag){
        cout << "chu ti zhe ying gai xue yi xia e long" << ed;
    }
}


int main()
{
    
    int _ = 1;
    cin >> _;
    
    while(_--) {
        solve();
    }
    
    return 0;
}