标签：机试题 make click bsp == tor template img init
题目链接：https://www.acwing.com/problem/content/605/
题目大意：
略
分析：
用dp[i][j]表示用j元钱能在前i只怪兽上所能贿赂到的最大武力值。
有一种情况就是打到第i只怪兽所需的最低花费大于j，那么令dp[i][j] = -1。
那么dp[i + 1][j]，也就是同样用j元钱能在前i + 1只怪兽上所能贿赂到的最大武力值是多少呢？有3种情况：
1：dp[i][j] = -1，显然dp[i + 1][j] = -1。
2：dp[i][j]
（1）：j
（2）：dp[i][j - p[i + 1]] == -1，这说明腾不出钱来，于是dp[i + 1][j] = -1。
（3）：dp[i][j - p[i + 1]] ！= -1，那么dp[i + 1][j] = dp[i][j - p[i + 1]] + d[i + 1]，不存在选择，必须贿赂。
3：dp[i][j] >= d[i + 1]，在这种情况下可以选择贿赂，也可以选择不贿赂，两种情况取最大即可，dp[i + 1][j] = max(dp[i][j], dp[i][j - p[i + 1]] + d[i + 1])。
递推关系有了，现在需要第0列的初始值：除了第0行，其他全部为-1；和第0行的初始值：全部为0。
那dp数组算出来了有啥用呢？
假设你打到第i个怪的时候，武力值为D，这时D = d[i]的j，这个j一定是打前i个怪最优的，因为花费比j小的金钱过不了这个boss，如果这个j能一直保持到游戏结束，那这个j就是总体最优的。
代码如下：
1 #pragma GCC optimize("Ofast")
2 #include 3 using namespace std;
4
5 #define INIT() std::ios::sync_with_stdio(false);std::cin.tie(0);
6 #define Rep(i,n) for (int i = 0; i 7 #define For(i,s,t) for (int i = (s); i 8 #define rFor(i,t,s) for (int i = (t); i >= (s); --i)
9 #define ForLL(i, s, t) for (LL i = LL(s); i 10 #define rForLL(i, t, s) for (LL i = LL(t); i >= LL(s); --i)
11 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
12 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)
13
14 #define pr(x) cout 15 #define prln(x) cout 16 #define EL() printf("\n")
17
18 #define SORT(c, s, t) sort(c + s, c + t + 1)
19
20 #define LOWBIT(x) ((x)&(-x))
21
22 #define ALL(x) x.begin(),x.end()
23 #define INS(x) inserter(x,x.begin())
24
25 #define ms0(a) memset(a,0,sizeof(a))
26 #define msI(a) memset(a,inf,sizeof(a))
27 #define msM(a) memset(a,-1,sizeof(a))
28
29 #define pii pair 30 #define piii pair,int>
31 #define MP make_pair
32 #define PB push_back
33 #define ft first
34 #define sd second
35
36 template 37 istream &operator>>(istream &in, pair &p) {
38 in >> p.first >> p.second;
39 return in;
40 }
41
42 template 43 istream &operator>>(istream &in, vector &v) {
44 for (auto &x: v)
45 in >> x;
46 return in;
47 }
48
49 template 50 ostream &operatorout, const std::pair &p) {
51 out "[" ", " "]" "\n";
52 return out;
53 }
54
55 typedef long long LL;
56 typedef unsigned long long uLL;
57 typedef pairdouble, double > PDD;
58 typedef setint > SI;
59 typedef vectorint > VI;
60 const double EPS = 1e-10;
61 const int inf = 1e9 + 9;
62 const LL mod = 1e9 + 7;
63 const int maxN = 1e5 + 7;
64 const LL ONE = 1;
65
66 //! n 表示怪兽的数量
67 //! d[i] 表示第i只怪兽的武力值
68 //! p[i] 表示收买第i只怪兽所需的金币数
69 //! ans 最小花费
70 int n, p[57], ans;
71 LL d[57];
72 //! dp[i][j] 表示用j元钱能在前i只怪兽上所能贿赂到的最大武力值
73 LL dp[57][107];
74
75
76 int main(){
77 INIT();
78 cin >> n;
79 For(i, 1, n) cin >> d[i];
80 For(i, 1, n) cin >> p[i];
81
82 For(i, 1, n) dp[i][0] = -1;
83
84 For(j, 1, 2 * n) {
85 For(i, 1, n) {
86 if(dp[i - 1][j] == -1) dp[i][j] = -1;
87 else if(dp[i - 1][j] d[i]) {
88 if(j 1;
89 else if(dp[i - 1][j - p[i]] == -1) dp[i][j] = -1;
90 else dp[i][j] = dp[i - 1][j - p[i]] + d[i];
91 }
92 else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - p[i]] + d[i]);
93 }
94 }
95
96 // maxD 最大武力值
97 // maxDi 最大武力值下标
98 LL maxD = -1, maxDi;
99 For(i, 1, n) {
100 if(d[i] > maxD) {
101 maxD = d[i];
102 maxDi = i;
103 }
104 }
105
106 ans = lower_bound(dp[maxDi], dp[maxDi] + 2 * n, maxD) - dp[maxDi];
107
108 cout endl;
109 return 0;
110 }
View Code
腾讯机试题 AcWing 603 打怪兽
标签：机试题 make click bsp == tor template img init
原文地址：https://www.cnblogs.com/zaq19970105/p/10742586.html