dp - 3维背包（东四省）
2024-09-06 17:25:46
题意：
给你 n 张卡片，总共可以消耗的法力值，求最多可以造成多少伤害， 卡片分为2种，一种是魔法卡，使用后可以使所有的连环卡的费用全部减1，另一种是连环卡，因魔法卡的使用可以使其费用减1，问最终最多可以造成多少的伤害
思路分析 ：
比赛的时候大脑短路了，基本不愿意去想东西了，导致题目没有出来，这个题就是一个 01背包，但是增加了一个限制条件，所以我们多增加一维表示到当前位置，所使用的魔法卡的数量，但是呢，还有一个很关键的地方，就是我们要先对卡片经行一个排序的预处理，这样在搞 dp的时候，才不会对后续有任何的影响，排序的时候，优先使用魔法卡，然后两者都是的卡，剩下的卡就随意了。
代码示例：（未测试）
#define ll long long
const int maxn = 1e6+5;
const int mod = 1e9+7;
const double eps = 1e-9;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f; int n, w; struct node
{
int w, x, p1, p2; }pre[505];
int dp[505][505][505];
int cnt = 0; bool cmp1(node a, node b){
if (a.p1 == b.p1) return a.p2 < b.p2;
return a.p1 > b.p1;
} bool cmp2(node a, node b){
if (a.w == b.w) return a.x > b.x;
return a.w < b.w;
} void fun(){ for(int i = 1; i <= n; i++){
for(int j = 1; j <= w; j++){
for(int k = 0; k <= min(i, cnt); k++){ // 使用魔法卡
if (pre[i].p1 && !pre[i].p2) { // 1 0
if (j >= pre[i].w && k)
dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-pre[i].w][k-1]+pre[i].x);
else dp[i][j][k] = dp[i-1][j][k];
}
else if (pre[i].p1 && pre[i].p2){ // 1 1
int cost = max(pre[i].w-k+1, 0);
//if (i == 2 && j == 2) printf("cost = %d\n", cost);
if (j >= cost && k){
dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-cost][k-1]+pre[i].x);
}
else dp[i][j][k] = dp[i-1][j][k];
}
else if (!pre[i].p1 && pre[i].p2){ // 0 1
int cost = max(pre[i].w-k, 0);
if (j >= cost && k){
dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-cost][k]+pre[i].x);
}
else dp[i][j][k] = dp[i-1][j][k];
}
else { // 0 0
if (j >= pre[i].w){
dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-pre[i].w][k]+pre[i].x);
}
else dp[i][j][k] = dp[i-1][j][k];
}
//printf("+++%d %d %d = %d \n",i, j, k, dp[i][j][k]);
}
}
}
} void init(){
int pos1 = -1, pos2 = -1; for(int i = 1; i <= n; i++){
if (pre[i].p1 && !pre[i].p2) {
pos1 = i;
break;
}
}
for(int i = n; i >= 1; i--){
if (pre[i].p1 && !pre[i].p2) {
pos2 = i;
break;
}
}
if (pos1 != -1) sort(pre+pos1, pre+pos2+1, cmp2); pos1 = pos2 = -1;
for(int i = 1; i <= n; i++){
if (pre[i].p1 && pre[i].p2) {
pos1 = i;
break;
}
}
for(int i = n; i >= 1; i--){
if (pre[i].p1 && pre[i].p2) {
pos2 = i;
break;
}
}
if (pos1 != -1) sort(pre+pos1, pre+pos2+1, cmp2); pos1 = pos2 = -1;
for(int i = 1; i <= n; i++){
if (!pre[i].p1 && !pre[i].p2) {
pos1 = i;
break;
}
}
for(int i = n; i >= 1; i--){
if (!pre[i].p1 && !pre[i].p2) {
pos2 = i;
break;
}
}
if (pos1 != -1) sort(pre+pos1, pre+pos2+1, cmp2); pos1 = pos2 = -1;
for(int i = 1; i <= n; i++){
if (!pre[i].p1 && pre[i].p2) {
pos1 = i;
break;
}
}
for(int i = n; i >= 1; i--){
if (!pre[i].p1 && pre[i].p2) {
pos2 = i;
break;
}
}
if (pos1 != -1) sort(pre+pos1, pre+pos2+1, cmp2);
} int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout); cin >> n >> w;
for(int i = 1; i <= n; i++){
scanf("%d%d%d%d", &pre[i].w, &pre[i].x, &pre[i].p1, &pre[i].p2);
if (pre[i].p1 == 1) cnt++;
}
sort(pre+1, pre+1+n, cmp1);
init();
for(int i = 1; i <= n; i++){
printf("%d%d%d%d\n", pre[i].w, pre[i].x, pre[i].p1, pre[i].p2);
}
memset(dp, 0x8f, sizeof(dp));
for(int j = 0; j <= w; j++) {
dp[0][j][0] = 0;
}
fun();
int ans = 0;
for(int i = 0; i <= cnt; i++) ans = max(ans, dp[n][w][i]);
printf("%d\n", ans);
return 0;
}
/*
4 3
1 3 0 1
1 0 0 0
3 3 1 1
3 4 1 0 3 3
3 3 1 1
2 3 1 1
1 3 1 1 3 4
3 10 1 1
30 400 1 1
4 200 1 1 5 5
6 50 1 1
3 30 0 1
3 3 1 0
3 200 0 0
3 6 1 0 6 4
1 3 1 0
2 5 0 0
1 2 0 1
2 2 1 1
3 4 0 1
1 1 1 0
*/
最新文章
- Socket网络编程一
- GitLab常见使用方法
- 意译：《JVM Internals》
- HTML5 Audio and Video 的新属性简介
- rh6安装oracle11g+ASM
- Nde模块篇
- 【转】简单的虚拟摇杆控制移动（NGUI）
- UVa 11624，两次BFS
- 对付ring0 inline hook
- 【转】（DT系列三）系统启动时, dts 是怎么被加载的
- 射频识别技术漫谈(14)——Mifare S50与S70的存取控制
- 认识到了x64程序的必要性
- ural 1118. Nontrivial Numbers
- Python之数据序列化（json、pickle、shelve）
- 基于SSE实现的极速的矩形核腐蚀和膨胀（最大值和最小值）算法。
- cug-day02
- windows配置openssl
- git冲突Please move or remove them before you can merge
- IntelliJ IDEA安装bower
- 数据库的相关语句（where，order by）