释放犯人解题报告 制作人：李晨曦 成章实验中学275班.

Presentation on theme: "释放犯人解题报告 制作人：李晨曦 成章实验中学275班."— Presentation transcript:

1 释放犯人解题报告 制作人：李晨曦 成章实验中学275班

2 题目来源 http://begin.lydsy.com/JudgeOnline/problem.php?cid=1101&pid=9
题目分析 这题的大意就是有一个王国，监狱需要释放m个犯人，一共有n个犯人。 首先我们知道，犯人之间可以传话（真强），若是一个犯人被释放周围的人就可以 知道，并且一个接一个传下去，然后他们就会不高兴（太不安分了），需要买肉来 安抚（太容易满足了吧，没脑子，难怪会进监狱），求最少的卖肉钱，（这里很神 奇，一个人肉只要1块钱）。（讲的太差，不如自己看题，我也懒得删） 若是其中有人被释放了（即那个地方为空），边上的人再传话就传不下去了（总不 能隔空传话吧）。

3 解题方法 f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]+j-i-1);
这道题我看到网上有用合并类dp来写的，还有用记搜的，我选择的是区间dp 我们可以选择用一个f的二维数组来存储当前的释放犯人所花的最小价值 如：f[i][j]代表[i,j]这个区间释放完犯人的最小价值 思路我也不好讲，就给大家解释一下状态转移方程 f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]+j-i-1); 说实话，这个状态转移方程我也不好用文字讲，所以，我只能用一组数据来表达一 下。 至少，好懂一点

4 丢样例 解释：s数组是一个类似前缀和的东西（但不是）
n=20,m=3; a[1]=3,a[2]=6,a[3]=14 我们可以看成 1……3……6……14……20 边界列出来更好表达 一次处理s[0]=0,s[1]=2,s[2]=2,s[3]=7,s[4]=6; 二次处理s[1]=2,s[2]=4,s[3]=11,s[4]=17; 处理的核心代码(结合上面，自己思考) for(int i=1;i<=m;i++) s[i]=a[i]-a[i-1]-1; s[m+1]=n-a[m]; for(int i=1;i<=m+1;i++) s[i]=s[i]+s[i-1];

5 f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]+j-i-1)
假如前面已经理解，我就来解释一下这里的状态转移方程吧（虽然可能是天书） f[i][k]+f[k+1][j]这个在区间dp里很常见了i是区间左端点，j是右端点，这就是枚 举其中最小的价值。s[j]-s[i-1]也很好看懂，不好讲，结合前面可以懂 j-i-1看上去有些不可理解，实际上就是把其中没算到的犯人加上去罢了 前面的s数组没有考虑先后被释放的顺序,所以同意没有考虑要被释放的犯人，这 里的处理就是如果释放后面的犯人时前面的犯人如果还没被释放，就把它加上去 接下来不懂得可以对照后面的代码

6 参考代码

7 龙浩然神犇友情赞助合并类写法 若要代码，联系本人 来自龙浩然原话

8 谢谢大家的支持！ 再次感谢同队的龙神犇，给予我的友情赞助，还有同队的欧力铭，韩志峰，鼓励我！
谢谢大家的支持！ 再次感谢同队的龙神犇，给予我的友情赞助，还有同队的欧力铭，韩志峰，鼓励我！