[DP][扫描线][思维] Codeforces 1313D Happy New Year

题目链接

题意:

有 $m$ 个小朋友,圣诞老人有 $N$ 个咒语,第 $i$ 个咒语施展出来的话,可以给 $[Li,Ri]$ 范围内的小朋友一块糖果,对每个小朋友来说,他得到的糖如果是奇数的话就会happy,否则就会不happy。

现在要求求出当圣诞老人采取某种最优的施展咒语的策略(一些用了一些没用,具体不需要求出来)的时候,最多有多少个小朋友可以happy?

题目保证,每个小朋友最多被 k 个咒语覆盖到。

数据范围: $m \le 10^9$, $N \le 10^5$, $1 \le k \le 8$, $1 \le Li \le Ri \le m$

题解:

(先吐槽下这题竟然2600分,这可是个div2D)

用扫描线的思想来做。

假设有一根竖直的扫描线在横轴上扫过去,那么他只会在每个 $[Li,Ri]$ 段的头尾两端发生状态变化,我们设置这些点为关键点,当我们采取某种特定的策略的时候,两个关键点之间的数据是不会发生变化的。

由于每个点最多被 $k$ 个线段覆盖,我们可以暴力的枚举出来当前扫描到的点的状态,即它被多少种线段覆盖到了,这个状态显然可以用二进制位来表示。由于我们是一个一个关键点找过去的,而两个关键点之间的数据状态仅由前一个点即可确定,所以我们的dp转移只需要考虑前一个点。

具体的转移:设 $dp[i][S]$ 为考虑到了第i个关键点(按从小到大的顺序),覆盖当前点的线段状态为 $S$ 的时候,最优解是多少。

  1. 当当前点为某线段的起点时,我们考虑每个 $S$ 中是否包含了第 $i$ 条线段,如果
    • 包含了,那么 $dp[i][S]=dp[i-1][S^(1<<p)]+(i到第i+1个关键点的距离)*(S中二进制位为1的奇偶性)$ ,因为我们相当于加上了新的一段;(其中p为当前线段所应在的二进制位,下同)
    • 没包含,那么$dp[i][S]=dp[i][S]$ $+(i到第i+1个关键点的距离)*(S中二进制位为1的奇偶性)$,等于说我们的扫描线在这一段仍然是按照之前的状态在扫描。
  2. 当当前点为某线段的终点时,我们仍然考虑每个 $S$ 中是否包含了第 $i$ 条线段,如果
    • 包含了,由于这条线段到此我们认为结束了,所以这种状态根本不合法,直接设置为$-INF$
    • 没包含,那么$dp[i][S]=max(dp[i-1][S],dp[i-1][S^(1<<p)])$ $+(i到第i+1个关键点的距离)*(S中二进制位为1的奇偶性)$,因为我们前面一段可能选了大,也可能不选更大,我们需要取个最优解。

然后我们可以发现两个转移都有方向性,我们可以用滚动数组忽略掉第一维,也就是说状态数组可以只开 $dp[1<<8]$ 即可。

实现细节:

  • 使用同一个 $used[8]$ 数组来表示当前的二进制位都表示的是第几条线段,因为每过一个点只会有最多1个点发生变化,所以这种方法是非常简洁的,不用像很多写法一样重新映射。。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxn = 100005;

pair<int,int> pos[maxn*2];
int dp[(1<<8)+5],used[8];

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i){
        cin>>pos[2*i-1].first>>pos[2*i].first;
        pos[2*i-1].second=i,pos[2*i].second=-i;
        ++pos[2*i].first;//[l,r] next is [r+1,...
    }
    sort(pos+1,pos+1+2*n);
    for(int i=1;i<(1<<k);++i) dp[i]=-INF;
    for(int it=1,p,id,len;it<=(n<<1);++it){
        len=(it==(n<<1)?0:pos[it+1].first-pos[it].first);
        id=pos[it].second;
        if(id>0){//start
            for(int i=0;i<k;++i)
                if(!used[i]){
                    used[p=i]=id;
                    break;
                }
            for(int j=(1<<k)-1;j>=0;--j){
                if((j>>p)&1){
                    dp[j]=dp[j^(1<<p)]+len*__builtin_parity(j);
                }else{
                    dp[j]+=len*__builtin_parity(j);
                }
            }
        }else{//end
            for(int i=0;i<k;++i)
                if(used[i]==-id){
                    used[p=i]=0;
                    break;
                }
            for(int j=0;j<(1<<k);++j){
                if((j>>p)&1){
                    dp[j]=-INF;
                }else{
                    dp[j]=max(dp[j],dp[j^(1<<p)])+len*__builtin_parity(j);//choose or not
                }
            }
        }
    }
    cout<<dp[0];
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据