***SPOJ - GCJ1C09C Bribe the Prisoners【贿赂囚犯】

news/2024/3/4 10:40:38

原题链接

题目:
n 组测试数据,有p个人在监狱,要放出q个人,这些人的编号为a[1]~a[q],每放出一个人,他周围的人(两边连续的直到碰到空的监狱或者尽头)都要贿赂1枚金币,问最少花费多少金币。

思路:
dp[i][j]表示释放a[i]和a[j]之间的囚犯所需要的最少金币数。
初始化:dp[i][i+1]=0(因为a[i]和a[i+1]之间没有待释放囚犯),其他为INF。
动态方程:dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]) + a[j] - a[i] - 2
(a[k]为a[i]和a[j]之间的一名待释放放囚犯)

AC代码:

#include <iostream>
#include <cstdio>  
#include <algorithm>
#include <cmath>  
using namespace std; int n, p, q, a[105], dp[105][105];
int INF = 429496725;int main()
{int i, j, k, t;scanf("%d", &n);for(i = 1; i <= n; i++){for(j = 0; j <= q + 1; j++){fill(dp[j], dp[j] + 1 + q, INF);}scanf("%d %d", &p, &q);for(j = 1; j <= q; j++){scanf("%d", &a[ja]);}a[0] = 0;a[q + 1] = p + 1;for(j = 0; j <= q; j++){dp[j][j + 1] = 0;} for(j = 2; j <= q + 1; j++){  //间隔j for(k = 0; k + j <= q + 1; k++){  //释放a[k]到a[k + j]之间需释放的囚犯 int bribe = INF;for(t = k + 1; t < k + j; t++){bribe = min(bribe, dp[k][t] + dp[t][k + j]);}dp[k][k + j] = bribe + a[k + j] - a[k] - 2; //两端不算(-1),被释放的囚犯不算(-1) }}printf("Case #%d: %d\n", i, dp[0][q + 1]);} return 0;
}

http://www.ppmy.cn/news/904918.html

相关文章

【bzoj1087】[SCOI2005]互不侵犯King

传送门&#xff1a;戳这里看题面 解题思路 dp[i][j][k] 表示到第i行为止&#xff0c;用了j个国王&#xff0c;且第i行的排列方式是k的总方案数 因为第i行的状态只与第i-1行和第i1行有关&#xff0c;所以只要从上到下dp&#xff0c;并预处理 c1[i] 和 c2[i][j] 分别表示状态i…

Bugku:加密 托马斯.杰斐逊

打开这道题就有点厉害&#xff0c; 百度了一下&#xff0c;这个人物&#xff0c;发现是轮转密码或者比尔密码【并不懂 首先观察了一下&#xff0c;最开始的1-14应该表示的是密码表&#xff0c;然后有密钥&#xff0c;就是用密钥的顺序调整密码表&#xff0c;然后用密文进行旋转…

88 FBI树

88 FBI树 作者: Turbo时间限制: 1S章节: 深度优先搜索 问题描述 : 我们可以把由“0”和“1”组成的字符串分为三类&#xff1a;全“0”串称为B串&#xff0c;全“1”串称为I串&#xff0c;既含“0”又含“1”的串则称为F串。   FBI树是一种二叉树&#xff0c;它的结点类型…

[BUUCTF misc]面具下的flag

&#xff08;菜鸡的misc之路qwq&#xff09; 解压压缩包得到一张.jpg图片 习惯性的用WinHex打开&#xff0c;发现并不是以.jpg的文件尾FF D9结尾 搜索一下FF D9&#xff0c;发现了在其后为50 4B 03 04&#xff0c;于是可以判断图片内隐藏了一个压缩包 将50 4B 03 04后的内…

转换到coff期间_fatal error LNK1123: 转换到 COFF 期间失败: 文件无效或损坏 | Lellansin's 冰森...

解决方案1: 原来机器上安装了VS2010非常正常,安装VS2012后,出现提示 错误 13 error LNK1123: 转换到 COFF 期间失败: 文件无效或损坏 出现的具体原因是微软的链接文件的格式变了(让人无语的微软) 解决方案2: 是嵌入清单的问题,于是对该工程以及所有依赖工程进行如下操…

P1087 FBI树 题解

来源洛谷ing 题目描述 我们可以把由“00”和“11”组成的字符串分为三类&#xff1a;全“00”串称为BB串&#xff0c;全“11”串称为I串&#xff0c;既含“00”又含“11”的串则称为F串。 FBIFBI树是一种二叉树&#xff0c;它的结点类型也包括FF结点&#xff0c;BB结点和I结点…

利用FbinstTool+大白菜u盘工具,制作多系统启动U盘【转】

一般制作多系统启动盘的教程都会要用到rub4dosgrubinstultraisomsgdiyerl等等工具&#xff0c;一大串的工具列表让人望而生畏。其实大白菜里已经对这些工具做了非常好的封装&#xff0c;利用大白菜FbinstTool&#xff0c;我们就可以方便的制作出功能丰富的启动U盘。 一、准备工…

【SCOI2005】【BZOJ1087】互不侵犯King

我天生不喜欢Dp就算你是状压DP… Description 在NN的棋盘里面放K个国王&#xff0c;使他们互不攻击&#xff0c;共有多少种摆放方案。国王能攻击到它上下左右&#xff0c;以及左上左下右上右下八个方向上附近的各一个格子&#xff0c;共8个格子。 Input 只有一行&#xff0…

fatal error C1189: #error : file must be compiled with _AFXDLL

1>D:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\atlmfc\include\afxdllx.h(55): error C2039: “m_pClassInit”: 不是“AFX_MODULE_STATE”的成员 1> D:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\atlmfc\include\afxstat_.h(210) : 参…

假冒CIA (中央情报局) 专题成员进行sextortion勒索诈骗

下面提到的将会是一种称为 sextortion 的攻击案例 通常这样的案例又称为性勒索或称性敲诈&#xff08;sextortion&#xff09;&#xff0c;这些骗子会在交友网站与受害者聊天&#xff0c;聊久了取得信任后就会循问对方&#xff0c;是否有意愿将聊天平台转移至 Skype 或其他外部…

[BUUCTF misc]Mysterious

如题&#xff1a; 下载附件得到一个可执行文件 题目中说打开逆向思维&#xff0c;第一时间想到用逆向工具IDA&#xff0c;先用32位的IDA分析&#xff08;如果不行换64位的&#xff09;&#xff0c;shiftF12定位关键字符串“well done” 定位关键函数 打开关键函数sub_401090并F…

bugku misc-where is flag 番外片

得到题目压缩包&#xff0c;&#xff0c;出题人说借鉴了where is flag系列的部分思路&#xff0c;注意到crc32和时间都没获得有效信息&#xff0c;所以把重点放在文件大小上 不过不管是文件大小还是压缩后大小&#xff0c;直接看不出东西&#xff0c;但是如果用文件大小减去压…

FBI:勒索软件是可怕的,但另一个骗局正在使受害者付出更多代价

电子邮件仍然是组织面临的最大威胁。 根据联邦调查局&#xff08;FBI&#xff09;互联网犯罪中心&#xff08;IC3&#xff09;的数据&#xff0c;商业电子邮件入侵&#xff08;BEC&#xff09;仍然是最大的财务损失来源&#xff0c;2021年总计24亿美元&#xff0c;高于2020年的…

fbinstool linux iso,大神给你传授fbinsttool下载 【操作教程】 的详细_

近日有小伙伴发现电脑出现问题了,在突然遇到fbinsttool下载 时不知所措了,对于fbinsttool下载 带来的问题,其实很好解决fbinsttool下载 带来的问题,下面小编跟大家介绍fbinsttool下载 解决方法: FbinstTool怎么用 答:1、请选择你要操作的U盘,这一步非常重要,选错盘,会…

Bullshit, Mr. Frankfurt!

Bullshit, Mr. Frankfurt! by pongba (http://blog.csdn.net/pongba) It was literally like stepping on a load of bullshit (at first I was going for “crap”, but then I thought it would be too impolite not to use the word “bullshit” you had proved so powe…

诡异的encountered unrecognized patch id:FMJJ,看不见的因果

单位的几台外网weblogic应用服务器&#xff0c;由于未修复WSAT组件RCE漏洞&#xff0c;导致受到攻击. 找了oracle原厂过来升级weblogic&#xff0c;一些不重要的系统便留给了我练练手。 结果第一台服务器就遇到问题了&#xff0c;weblogic版本是10.3.3&#xff0c;需要先升到…

《犯罪心理学》读书笔记(part5)--犯罪心理的形成与内在因素的影响(下)

学习笔记&#xff0c;仅供学习 文章目录 犯罪心理的形成与内在因素的影响犯罪动机犯罪动机的转化不明显的犯罪动机 犯罪者的智力特征智力描述智力犯罪 犯罪者的气质特征气质的概念气质与犯罪 犯罪者的情绪、意志特征情绪的概念和分类不良情绪与犯罪情绪障碍与犯罪意志的一般概念…

【NOIP】FBI树

【NOIP】FBI树 题目 题目描述 我们可以把由“0”和“1”组成的字符串分为三类&#xff1a;全“0”串称为B串&#xff0c;全“1”串称为I串&#xff0c;既含“0”又含“1”的串则称为F串。 FBI树是一种二叉树&#xff0c;它的结点类型也包括F结点&#xff0c;B结点和I结点三…

[转载]FBI索引

[转载]FBI索引 http://www.look4bug.com/Items/xtzq/...00-299/286.htmlfbi索引--->[作者:net] Oracle8i的很重要的一个新特性就是增加了function-based index这种索引类型(后面简称为FBI)。有了这个特性后,Oracle DBA就可以在索引中使用函数或者表达式了。这些函数可…

SDNUOJ 1168.FBI树

Problem - 1168 (sdnu.edu.cn) 1168.FBI树 我真牛逼&#xff01;算是第一个自主想出来的线段树。 我们可以把由“0”和“1”组成的字符串分为三类&#xff1a;全“0”串称为B串&#xff0c;全“1”串称为I串&#xff0c;既含“0”又含“1”的串则称为F串。 FBI树是一种二叉树…
最新文章