日暮寻路题解-创新互联

描述

“先生，您是什么人，要去哪里？”
“天已经快黑了，您要去哪里？”

玛恩纳是明日方舟里的一位强大的干员。

玛恩纳有两种状态:

1. 第一种为暖机状态，期间玛恩纳不能开技能，不能攻击。暖机时间为不包括上一次技能结束时刻的F个时刻。即若玛恩纳在第ii时刻结束技能，那么玛恩纳在第[i + 1,i+ F][i+1,i+F]内的时刻都不能开技能。
2. 第二种为开启技能状态。包括技能开启时刻的接下来K个时刻，玛恩纳都会对攻击范围内所有敌人造成 1 点伤害。例如从第4时刻开启技能，K = 7，那玛恩纳会在第4、5、6、7、8、9、10时刻攻击。

注意事项

1. 战斗开始时，玛恩纳可以在任意时刻开启技能。技能结束后，玛恩纳会进入暖机状态，持续F个时刻。暖机时间结束后，可以继续选择在接下来的某一时刻开启技能。
2. 给出 nn个敌人的在玛恩纳攻击范围的起始时刻和结束时刻Li​ ,Ri​ ，特别的所有敌方单位的生命值 H=R i​ −L i​ +1。

开始时刻为第 11 秒，结束时刻为第 TT 秒，问如何规划技能开启时间可以使玛恩纳最多能杀死多少敌方单位。

输入样例 1
5 20 7 3
4 6
10 12
11 14
13 17
4 10
输出样例 1
3

这题一个重点就是以时刻为单位来看比较好理解，从题意可知是从第1秒开始的。

然后遍历每个敌人，满足上图条件的val[i]的价值加1,利用差分进行优化。

再利用前缀和把val数组求出来

#includeusing namespace std;
int main()
{int n,t,k,f;
    cin>>n>>t>>k>>f;
    int chafen[t+1];
    memset(chafen,0,sizeof(chafen));
    for(int i=1;i<=n;i++)
    {int l,r,xue;
        cin>>l>>r;
        xue=r-l+1;
        if(r-l+1>k)continue;
        int h=max(1,r-k+1);
        chafen[h]++;
        chafen[l+1]--;
    }
    int val[t+1];
    memset(val,0,sizeof(val));
    for(int i=1;ival[i]=val[i-1]+chafen[i];
    }
    int res[t+1];
    memset(res,0,sizeof(res));
    for(int i=1;iint y=max(0,i-k-f);
        res[i]=max(res[i-1],res[y]+val[i]);
    }
    cout<