文档章节

poj1015 Jury Compromise - dp,背包模型

m2012
 m2012
发布于 2012/05/27 08:34
字数 580
阅读 175
收藏 0

以前年少无知,看到这题觉得无从入手,今天,终于看出来,这是一道背包题。

每个人,只有选和不选,如果选了,就会影响某个资源的值,而且人与人之间的顺序不影响答案,这种类型的题目,果断就是背包了。

 

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstdlib>
using namespace std;

int like[202];
int dislike[202];
int N, M;
int f[200 + 1][20 + 1][1600 + 2];
char pre[200 + 1][20 + 1][1600 + 2];
vector<int> ansList;
int testN;


const int nil = -2000000;
int dp(int n, int m, int d) {
  // printf("==== %d %d %d\n", n, m, d);
  return f[n][m][d + 800];
}



void input() {
  int i, j, k;
  scanf("%d %d", &N, &M);
  if (N == 0) exit(0);
  for (i = 1; i <= N; ++i) {
    scanf("%d %d", &(like[i]), &(dislike[i]));
  }


  for (i = 0; i < 201; ++i)
    for (j  = 0; j < 20 + 1; ++j)
      for (k = 0; k < 1600 + 2; ++k) {
        f[i][j][k] = nil;
        pre[i][j][k] = 'w';
      }
}


void traceBack(int n, int m, int d) {
  while (1) {
    char & son = pre[n][m][d + 800];
    // printf("*** %d %d %d %c\n", n, m, d, son);

    assert(n >= 1);

    if (son == '+') {
      ansList.push_back(n);
      d = d - (like[n] - dislike[n]);
      n = n - 1;
      m = m - 1;
      continue;
    }

    if (son == '-'){
      n = n - 1;
      continue;
    }

    if (son == 'e') break;
    if (son == 'E') {
      ansList.push_back(1);
      break;
    }

    assert(0);

  }
}



void run() {
  input();

  int n, m, d;
  for (n = 1; n <= N; ++n) {
    for (m = 0; m <= n && m <= M; ++m) {
      for (d = -800; d <= 800; ++d) {
          int & ans = f[n][m][d + 800];
          char & son = pre[n][m][d + 800];

          if (n == 1) {
            if (m == 0) {
              if (d == 0) { son = 'e'; ans = 0; continue; }
              else { son = 'x'; ans = -1; continue; }
            } else if (m == 1) {
              if (d == like[1] - dislike[1]) { son = 'E'; ans = like[1] + dislike[1]; continue; }
              else { son = 'y'; ans = -1; continue; }
            }

            assert(0);
          }

          ans = -1;
          son = 'p';
          int c = like[n] - dislike[n];
          if (n - 1 >= m && dp(n - 1, m, d) != -1) {
            ans = dp(n - 1, m, d);
            son = '-';
          }

          if (n >= m && m >= 1 && dp(n - 1, m - 1, d - c) != -1 && (ans == -1 || ans < dp(n - 1, m - 1, d - c) + like[n] + dislike[n]) ) {
            ans = dp(n - 1, m - 1, d - c) + like[n] + dislike[n];
            son = '+';
          }
      }
    }
  }


  int i, ans;
  for (i = 0; i <= 800; ++i) {
    if (dp(N, M, i) != -1 && dp(N, M, -i) == -1) {
      ans = i;
      break;
    }
    if (dp(N, M, i) == -1 && dp(N, M, -i) != -1) {
      ans = -i;
      break;
    }
    if (dp(N, M, i) != -1 && dp(N, M, -i) != -1 && dp(N, M, i) >= dp(N, M, -i)) {
      ans = i;
      break;
    }
    if (dp(N, M, i) != -1 && dp(N, M, -i) != -1 && dp(N, M, i) < dp(N, M, -i)) {
      ans = -i;
      break;
    }
  }



  ansList.clear();
  traceBack(N, M, ans);

  printf("Jury #%d\n", testN);
  printf("Best jury has value %d for prosecution and value %d for defence:\n",  (ans + dp(N, M, ans))/2,  -(ans - dp(N, M, ans))/2);

  sort(ansList.begin(), ansList.end());
  for (i = 0; i < ansList.size(); ++i) {
    printf(" %d", ansList[i]);
  }
  printf("\n\n");
}


int main() {
  for (testN = 1; true; ++testN)
    run();
  return 0;
}

© 著作权归作者所有

共有 人打赏支持
下一篇: poj 其他
m2012
粉丝 16
博文 129
码字总数 52548
作品 0
广州
程序员
私信 提问
动态规划 &

一、 动态规划(Dp问题):解决问题的关键点 1) 递推公式:(最有子结构) 2) 数据的初始化 用例分析: a. 01 背包的问题(Knapsack Problem) 定义: 一个背包的容量V; 存在N个物品:w[i...

Playboy002
2015/07/17
42
0
百练 4102 宠物小精灵之收服 【二维费用背包】

传送门 // 题意: 有k个怪物, 告诉每个怪物捕捉它需要的精灵球和皮卡丘收到的伤害, 给定精灵球的一共的数量和皮卡丘总的体力值, 问最多可以捕捉到多少个怪物, 然后如果能捕捉到的怪物相同则要...

anxdada
2018/03/08
0
0
洛谷 ~ P2014 ~ 选课 (树形背包)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/ZscDst/article/details/85002210 思路 树形背包的模板题。加一个虚拟的0结点然后选m+1个科目就OK。...

张松超
2018/12/14
0
0
HDU 2602 Bone Collector(01背包)

Bone Collector   Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s ,......

suvvm
2018/11/08
0
0
HDU 2191 悼念512汶川大地震遇难同胞

悼念512汶川大地震遇难同胞   急!灾区的食物依然短缺!   为了挽救灾区同胞的生命,心系灾区同胞的你准备自己采购一些粮食支援灾区,现在假设你一共有资金n元,而市场有m种大米,每种大...

suvvm
2018/11/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Vert.x系列(二)--EventBusImpl源码分析

前言:Vert.x 实现了2种完成不同的eventBus: EventBusImpl(A local event bus implementation)和 它的子类 ClusteredEventBus(An event bus implementation that clusters with other Ve......

冷基
37分钟前
1
0
Perl - 获取文件项目

参考:http://www.runoob.com/perl/perl-directories.html 下面返回JSON格式的文件列表 #!/usr/bin/perluse strict;use warnings;use utf8;use feature ':5.26';require Fi......

wffger
昨天
2
0
vue组件系列3、查询下载

直接源码,虽然样式样式不好看,逻辑也不是最优,但是可以留作纪念。毕竟以后类似的功能只需要优化就可以了,不用每次都重头开始。。。 <template> <div class="pre_upload"> <div ...

轻轻的往前走
昨天
2
0
java浅复制和深复制

之前写了数组的复制,所以这里继续总结一下浅复制和深复制。 浅拷贝:对基本数据类型进行值传递,对引用数据类型进行引用传递般的拷贝。 深拷贝:对基本数据类型进行值传递,对引用数据类型,...

woshixin
昨天
1
0
kubernetes 二进制包安装

环境 角色 主机名 内网 IP 集群 IP 操作系统 服务 执行目录 部署机 k8s-master master120 10.0.4.120 - CentOS kube-apiserver kube-scheduler kube-controller-manager /opt/kubernetes/ et......

Colben
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部