传送门
分析
这转化，真是够可以的
首先我们需要得出一个结论：无论我们怎么选，最后肯定都有一种选法满足条件（证明的话，感性理解一下，假设我们现在知道最后打出去的牌是哪些，那我们一定可以调整打牌的顺序，使其满足条件） 然后在此基础上我们就可以直接使用0/1背包 将伤害值看做是原牌的价值，魔法值看做是原牌的体积
代码
#include<bits/stdc++.h>
#define in read()
#define N 100009
using namespace std
;
inline int read(){
int ans
=0;
char ch
=getchar();
while(!isdigit(ch
))ch
=getchar();
while(isdigit(ch
))ans
=(ans
<<3)+(ans
<<1)+(ch
^48),ch
=getchar();
return ans
;
}
int n
,m
;
int val
[N
],c
[N
],f
[N
];
int main(){
n
=in
;
int i
,j
,k
;
for(i
=1;i
<=n
;++i
){
val
[i
]=in
;c
[i
]=in
;
}
for(i
=1;i
<=n
;++i
)
for(j
=n
;j
>=c
[i
];--j
)
f
[j
]=max(f
[j
],f
[j
-c
[i
]]+val
[i
]);
int ans
=-1;
for(i
=1;i
<=n
;++i
)
ans
=max(ans
,f
[i
]);
cout
<<ans
;
return 0;
}
转载请注明原文地址: https://www.6miu.com/read-4931516.html
