AcWing 603. 打怪兽
原题链接
中等
作者:
Tie
,
2019-09-06 00:44:58
,
所有人可见
,
阅读 1306
#include <iostream>
#include <cstring>
using namespace std;
//C++ 超过10的8次幂,考虑LL
typedef long long LL;
const int N = 55, M = N * 2;
int n;
//f状态表示: 打i只怪兽,花j枚金币,买的怪兽的最大战斗力
//为什么f也要LL?这里是表示战斗力之和
LL d[N], f[N][M]; //M表示收买n只怪兽所需要的总共金币,每只怪兽最多2枚,所以用2N
int p[N]; //p[N] 表示收买i只怪兽所需的金币数(题目有误!),里面储存1 或 2, 所有P[N]和<=M;
int main()
{
//输入
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> d[i];
for (int i = 1; i <= n; i ++ ) cin >> p[i];
memset(f, -1, sizeof f);//初始化所有状态都是-1,因为f[N][1]一类的状态不满足
f[0][0] = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n * 2; j ++ )
{
//状态集合分成两部分,第一部分买第i只怪兽(1.金币数大于当前怪兽金币价值 2.保证状态合法才可以转移)
//第二部分不买第i只怪兽(1.保证状态合法才可以转移 2.前面怪兽能打得过新怪兽)
if (j >= p[i] && f[i - 1][j - p[i]] != -1) f[i][j] = f[i - 1][j - p[i]] + d[i];
if (f[i - 1][j] != -1 && f[i - 1][j] >= d[i]) f[i][j] = max(f[i][j], f[i - 1][j]);
}
// 遍历所有满足条件的金币状态,找出可以打n个怪兽的最小金币数
int res = 0;
for (int i = 1; i <= n * 2; i ++ )
if (f[n][i] != -1)
{
res = i;
break;
}
cout << res << endl;
return 0;
}