度度熊与邪恶大魔王
Accepts: 2016
Submissions: 12307
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
传送门: bestcoder
Problem Description
度度熊为了拯救可爱的公主，于是与邪恶大魔王战斗起来。
邪恶大魔王的麾下有n个怪兽，每个怪兽有a[i]的生命值，以及b[i]的防御力。
度度熊一共拥有m种攻击方式，第i种攻击方式，需要消耗k[i]的晶石，造成p[i]点伤害。
当然，如果度度熊使用第i个技能打在第j个怪兽上面的话，会使得第j个怪兽的生命值减少p[i]-b[j]，当然如果伤害小于防御，那么攻击就不会奏效。
如果怪兽的生命值降为0或以下，那么怪兽就会被消灭。
当然每个技能都可以使用无限次。
请问度度熊最少携带多少晶石，就可以消灭所有的怪兽。
本题包含若干组测试数据。
第一行两个整数n，m,表示有n个怪兽，m种技能。
接下来n行，每行两个整数，a[i],b[i]，分别表示怪兽的生命值和防御力。
再接下来m行，每行两个整数k[i]和p[i]，分别表示技能的消耗晶石数目和技能的伤害值。
数据范围:
1<=n<=100000
1<=m<=1000
1<=a[i]<=1000
0<=b[i]<=10
0<=k[i]<=100000
0<=p[i]<=1000
Output
对于每组测试数据，输出最小的晶石消耗数量，如果不能击败所有的怪兽，输出-1
1 2
3 5
7 10
6 8
1 2
3 5
10 7
8
Sample Output
Aceppted代码
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1020;
const ll INF=0x3f3f3f3f;
ll num[maxn][12];
ll dp[1020][15];
struct skill
{
ll hit;
ll price;
} a[maxn];
ll best[maxn];
ll min(ll a,ll b)
{
if(a>b)
return b;
else
return a;
}
void complete_packet(int k, int p)
{
for (int b = 0; b <= 10; ++b)
{
if (b >= p)
{
continue;
}
else
{
int d = p - b;
for (int a = 1; a <= d; ++a)
{
dp[a][b] = min(dp[a][b], k);
}
for (int a = d + 1; a <= 1000; ++a)
{
dp[a][b] = min(dp[a][b], dp[a - d][b] + k);
}
}
}
}
int main()
{
cin.sync_with_stdio(false);
ll n, m;
ll x, y;
ll max_def = -INF, max_hit = -INF;
while(cin >> n >> m)
{
max_def = -INF, max_hit = -INF;
memset(num, 0, sizeof(num));
memset(a, 0, sizeof(a));
memset(best, -1, sizeof(best));
memset(dp, 0, sizeof(dp));
for(ll i = 0; i < n; i++)
{
cin >> x >> y;
num[x][y]++;
if(y >= max_def)
max_def = y;
}
ll flag = 0;
for(ll i = 0; i < m; i++)
{
cin >> x >> y;
if(best[y] == -1)
{
a[flag].hit = y;
a[flag].price = x;
best[y] = x;
if(a[flag].hit > max_hit)
max_hit = a[flag].hit;
flag++;
}
else
{
if(x < best[y])
best[y] = x;
}
}
ll ans = 0;
ll temp = 0;
if(max_def >= max_hit)
cout << "-1" << endl;
else
{
for (int i = 0; i <= 1010; ++i)
{
for (int j = 0; j <= 10; ++j)
{
if (i == 0)
{
dp[i][j] = 0;
}
else
{
dp[i][j] = INF;
}
}
}
for(int i=0;i<flag;i++)
complete_packet(best[a[i].hit],a[i].hit);
for(ll i = 0; i < 1002; i++)
{
if(temp == n)
break;
for(ll j = 0; j < 12; j++)
{
if(num[i][j] != 0)
{
temp += num[i][j];
ans += dp[i][j]*num[i][j];
}
}
}
cout << ans << endl;
}
}
return 0;
}
|
