当前位置: 首页 > news >正文

[Poj 1015] Jury Compromise 解题报告 (完全背包)

题目链接:http://poj.org/problem?id=1015

题目:

题解:

我们考虑设计DP状态(因为这很显然是一个完全背包问题不是吗?)

dp[j][k]表示在外层循环到i时,选了j个人,此时辩方总分和控方总分差值为k的时,辩方和控方的总分的和的最大值

dp[j][k+a[i]-b[i]] = max (dp[j][k + a[i] - b[i]] , dp[j][k] + a[i] + b[i])

因为是完全背包,所以我们需要写一个search函数判断当前转移的状态是否已经选过了i,这样我们需要记录一个d[j][k]数组表示在dp[j][k]的状态是选哪一个人转移过来的,这恰好也是题目要求我们处理出来的

题解其实就是上述部分了

题外话:

我们考虑不写那个search函数,然后把j这一维倒序循环,根据《算法竞赛进阶指南》,这样的做法是可以的,但是笔者尝试之后还做不到,碰到的问题就是假设dp[j][k+a[i]-b[i]]被dp[j-1][k]转移得到,此时我们可以确定dp[j-1][k]这个状态没有选择i这个人。

但是在之后的循环中,dp[j-1][k]可能会被再次更新,我们要是只是统计答案的话这并没有什么影响,但是我们在d数组回溯的时候就会得到错误的转移,因为dp[j-1][k]可能被i更新,于是d[j-1][k]变成了i。补充:但是在我的AC代码里,显然是可以避免这种情况的,因为dp[j-1][k]不可能再被更新

除此之外,我发现i循环放在最外面是不行的。这是为什么?若是有读者知道请在评论区留言。

AC代码(加了search函数)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,fix,time;
int a[201],b[201],dp[201][801],d[201][801],id[201];
inline int read()
{
    char ch=getchar();
    int s=0,f=1;
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
    return s*f;
}
bool search(int j,int k,int i)
{
    while (j&&d[j][k]!=i)
    {
        int o=d[j][k];
        k-=a[o]-b[o];
        j--;
    }
    if (j) return false;
    return true;
}
int main()
{
    while (1)
    {
        n=read();m=read();
        if (!n) break;
        for (int i=1;i<=n;i++)
        {
            a[i]=read();b[i]=read();
        }
        memset(dp,-1,sizeof(dp));
        memset(d,0,sizeof(d));
        fix=m*20;
        dp[0][fix]=0;
        for (int j=1;j<=m;j++)
            for (int k=0;k<=fix<<1;k++)
                if (dp[j-1][k]>=0)
                {
                    for (int i=1;i<=n;i++)
                        if (dp[j-1][k]+a[i]+b[i]>dp[j][k+a[i]-b[i]]&&search(j-1,k,i))
                        {    
                            dp[j][k+a[i]-b[i]]=dp[j-1][k]+a[i]+b[i];
                            //if (j==3&&k+a[i]-b[i]==57&&k==58) printf("sdfs%d\n",d[j-1][k]);
                            d[j][k+a[i]-b[i]]=i;
                            //if (j==2&&k+a[i]-b[i]==58) printf("%d\n",i);
                        }
                }
        int k,div;
        for (int i=0;i<=fix;i++)
            if (dp[m][fix-i]!=-1||dp[m][fix+i]!=-1) {k=i;break;}
            //printf("%d\n",k); 
        div=dp[m][fix-k]>dp[m][fix+k]?(fix-k):(fix+k);
        printf("Jury #%d\n",++time);
        printf("Best jury has value %d for prosecution and value %d for defence:\n",(dp[m][div]+div-fix)/2,(dp[m][div]-div+fix)/2);
        int r=div;
        for (int i=1;i<=m;i++)
        {
            id[i]=d[m-i+1][r];
            r-=a[id[i]]-b[id[i]];
        }
        sort(id+1,id+1+m);
        for (int i=1;i<=m;i++) printf(" %d",id[i]);
        printf("\n\n");
    }    
     return 0;
}

 

转载于:https://www.cnblogs.com/xxzh/p/9561460.html

相关文章:

  • 第一次随笔
  • Makefile 使用总结
  • Django学习之五:Django 之 注意事项及汇总
  • HTTP 400 错误 - 请求无效 (Bad request)
  • BZOJ2326 HNOI2011数学作业(矩阵快速幂)
  • 暑假第八周进度总结
  • AngularJS 整理学习
  • ngnix——FastCGI 相关参数调优
  • jmeter 使用cookie管理器
  • 小米OJ刷题日志
  • 广义后缀自动机
  • 编程基本功训练:流程图画法及练习
  • Python入门学习-DAY36-GIL全局解释器锁、死锁现象与递归锁、信号量、Event事件、线程queue...
  • SqlMap使用
  • Maven打war包命令
  • Google 是如何开发 Web 框架的
  • [分享]iOS开发 - 实现UITableView Plain SectionView和table不停留一起滑动
  • [译]前端离线指南(上)
  • 【译】React性能工程(下) -- 深入研究React性能调试
  • 10个确保微服务与容器安全的最佳实践
  • ES6系列(二)变量的解构赋值
  • RxJS 实现摩斯密码(Morse) 【内附脑图】
  • SegmentFault 社区上线小程序开发频道,助力小程序开发者生态
  • Vue官网教程学习过程中值得记录的一些事情
  • 成为一名优秀的Developer的书单
  • 番外篇1:在Windows环境下安装JDK
  • 基于Javascript, Springboot的管理系统报表查询页面代码设计
  • 猫头鹰的深夜翻译:Java 2D Graphics, 简单的仿射变换
  • 前端学习笔记之原型——一张图说明`prototype`和`__proto__`的区别
  • 浅析微信支付:申请退款、退款回调接口、查询退款
  • 设计模式走一遍---观察者模式
  • 实习面试笔记
  • 适配iPhoneX、iPhoneXs、iPhoneXs Max、iPhoneXr 屏幕尺寸及安全区域
  • 我是如何设计 Upload 上传组件的
  • 在GitHub多个账号上使用不同的SSH的配置方法
  • Python 之网络式编程
  • 从如何停掉 Promise 链说起
  • !!Dom4j 学习笔记
  • #我与Java虚拟机的故事#连载06:收获颇多的经典之作
  • (PyTorch)TCN和RNN/LSTM/GRU结合实现时间序列预测
  • (vue)el-checkbox 实现展示区分 label 和 value(展示值与选中获取值需不同)
  • (超详细)语音信号处理之特征提取
  • (附源码)spring boot网络空间安全实验教学示范中心网站 毕业设计 111454
  • (五)关系数据库标准语言SQL
  • (学习日记)2024.01.19
  • (一)pytest自动化测试框架之生成测试报告(mac系统)
  • ***监测系统的构建(chkrootkit )
  • .NET Core IdentityServer4实战-开篇介绍与规划
  • .Net6使用WebSocket与前端进行通信
  • .net开发引用程序集提示没有强名称的解决办法
  • .pyc文件是什么?
  • @FeignClient注解,fallback和fallbackFactory
  • @JsonFormat与@DateTimeFormat注解的使用
  • @RequestMapping用法详解
  • @RequestParam,@RequestBody和@PathVariable 区别