【每日一题】Moovie Mooving
Moovie Mooving
https://ac.nowcoder.com/acm/problem/24158
先回答邓老师的问题：写英文题真的真的真的，很痛苦QAQ
题目描述：
输入描述：
输入的第一行包含N和L。
输出描述：
一个整数，指示Bessie实现其目标所需观看的最少电影数量。如果这不可能，则输出-1。
题目
题目描述： Bessie去看电影了。由于一如既往的调皮，她决定对农夫John隐瞒L（1 <= L <= 100,000,000）分钟，在此期间她想连续看电影。
她有N部电影（1 <= N <= 20）可供选择，每部电影都有一定的时长和白天的放映时间。
贝西（Bessie）可以在电影放映时间中的任何时间进入和退出电影，但是她不希望两次访问同一部电影，并且她不能切换到与当前放映时间重叠的同一部电影的另一部放映时间。
帮助贝西确定是否有可能实现从时间0到时间L连续观看电影的目标。
如果是，请确定达到此目标所需观看的最***数量（Bessie与情节线混淆了如果她看了太多电影）。
输入的第一行包含N和L。
接下来的N行分别描述电影。
它们以其整数持续时间D（1 <= D <= L）和放映时间数C（1 <= C <= 1000）开始。
同一行上其余的C个整数分别在0.……L范围内，并给出了电影上映之一的开始时间。
放映时间各不相同，范围为0..L，并且以递增顺序给出。
一个整数，指示Bessie实现其目标所需观看的最少电影数量。如果这不可能，则输出-1。
解析
这道题的可以很简单的看出来是一道dp的题目。
- 那么还是这句话：动态规划最重要的就是递推和dp数组的含义。
那么我们就先来探讨一下数组的含义：
- 根据题目的数据范围，我们首先发现，dp枚举L（时间）是不可能的，因为L太大了，数组放不下。
- 于是盲僧们就发现了华点。我们的电影范围很小，所以我们应该按电影进行dp。
- 所以这里就又是我一个第一次碰到的知识点：状态压缩dp。
状态压缩dp：
- 首先我们来讲一下状压dp是什么原理吧：类似于二进制枚举，我们将每一个整数看成一个二进制数，二进制的每一位表示一种情况是否存在。
- 所以假如有n种情况，我们所要使用的数字大小就有2n如此之多。所以我们在情况基数小的时候就可以使用这种方法。
- 举个栗子（详细情况依旧是看电影）：我们现在的dp[pos] = num中的pos = 13，13的二进制为1101，我们从低位向高位数。我们就发现我们看了第一，三，四场电影。
- 还是上面这个栗子，我们dp数组的意义是什么呢？就是在某种电影观看情况（pos的二进制表示）下，最长的电影连续时间（num）。
既然我们了解了算法，我们就要操作了：
- 就和普通背包dp一样，我们从头向后遍历，然后再判断是否要进行最大值替换（判断是否可以有情况内利用更加充分的方法）。
- 然后怎么替换也挺重要的：我们先确定一种情况，然后对每一场电影进行替换（先将这个场次进行删除，假设删除之后的场次情况为k）。
- 我们删除以后的东西是什么意思呢？k是删除后的场次情况的话，我们此时的dp[k]就是指在删除这一场电影之后的电影结束放映时间。
- 我们就替换一部新的，开播时间在该电影之前的电影，比较一下哪部电影看起来更长，长就换上去（因为电影越长，我们最后看的场次就会越少）。
以上就是我们的dp过程了，然后就剩下打代码了：
- 首先我们要将该存的存下来，我们用一个二维数组存放我们的开播情况。
- 然后按照我们上面的进行递推。
- 接下来呢，我们有要求，要在看电影上花光所有时间，所以从电影连续时间（dp数组的值）大于l的数据里面找出电影场次最小值就好了。
- 我们简单讲一下电影场次数的求法，也就是求二进制中1的个数，这个并不难，但是我们要了解一种新的求法：
int count(int x) { int cnt = 0; while (x) { cnt++; x -= x & -x; } return cnt; }我们这里最主要的就是：x & -x是什么东西？简单来说，就是由最低位的1和后面的0组成的数。假如x = 10010，这个就是10（十进制就是2）。
每次减掉不就相当于删掉了一个最小位的1了吗。所以是一种把1从低位到高位删掉的方法。 - 找到最小值判断一下我们这个是不是能看完所有的时间（最小值为初始化的极大值INF），然后判断输出就好了。
- 看代码咯~
AC代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
#define IOS ios::sync_with_stdio(false);
//代码预处理区
const int INF = 0x3f3f3f3f;
const int MAX = 27;
int D[MAX], dp[1 << 21];//持续时间，dp数组（最大20）
vector<int> C[MAX];//开播情况
//全局变量区
int count(int x) {
int cnt = 0;
while (x) {
cnt++;
x -= x & -x;
}
return cnt;
}
//函数预定义区
int main() {
IOS;
int n, l; cin >> n >> l;
for (int i = 0; i < n; i++) {
int tmp; cin >> D[i] >> tmp;
for (int j = 1; j <= tmp; j++) {
int t; cin >> t;
C[i].push_back(t);
}
}
//初始化条件
int ans = INF;
memset(dp, 0, sizeof dp);
for (int way = 1; way < 1 << n; way++)
for (int i = 0; i < n; i++)
if (way >> i & 1) {
int k = way ^ (1 << i);//删除该位（变成0），其他不变
int pos = upper_bound(C[i].begin(), C[i].end(), dp[k]) - C[i].begin() - 1;
//查找出小于等于dp[k]（k情况下电影最长结束时间）中最大的位置（能找到一个替换的）
if (pos >= 0) dp[way] = max(dp[way], C[i][pos] + D[i]);
//判断有没有这个位置（可以用来替换的），然后比较替换值
}
//递推
for (int way = 1; way < 1 << n; way++)
if (dp[way] >= l)
ans = min(ans, count(way));
if (INF == ans) cout << "-1" << endl;//不能连贯看完
else cout << ans << endl;
return 0;
}
//函数区 每日一题 文章被收录于专栏
憨憨的专栏
查看12道真题和解析