題目

描述

創(chuàng)新互聯(lián)是專業(yè)的丹東網(wǎng)站建設(shè)公司，丹東接單;提供網(wǎng)站設(shè)計(jì)、成都做網(wǎng)站,網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行丹東網(wǎng)站開(kāi)發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛(ài)的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來(lái)合作!

“先生，您是什么人，要去哪里？”
“天已經(jīng)快黑了，您要去哪里？”

瑪恩納是明日方舟里的一位強(qiáng)大的干員。

瑪恩納有兩種狀態(tài):

1. 第一種為暖機(jī)狀態(tài)，期間瑪恩納不能開(kāi)技能，不能攻擊。暖機(jī)時(shí)間為不包括上一次技能結(jié)束時(shí)刻的F個(gè)時(shí)刻。即若瑪恩納在第ii時(shí)刻結(jié)束技能，那么瑪恩納在第[i + 1,i+ F][i+1,i+F]內(nèi)的時(shí)刻都不能開(kāi)技能。
2. 第二種為開(kāi)啟技能狀態(tài)。包括技能開(kāi)啟時(shí)刻的接下來(lái)K個(gè)時(shí)刻，瑪恩納都會(huì)對(duì)攻擊范圍內(nèi)所有敵人造成 1 點(diǎn)傷害。例如從第4時(shí)刻開(kāi)啟技能，K = 7，那瑪恩納會(huì)在第4、5、6、7、8、9、10時(shí)刻攻擊。

注意事項(xiàng)

1. 戰(zhàn)斗開(kāi)始時(shí)，瑪恩納可以在任意時(shí)刻開(kāi)啟技能。技能結(jié)束后，瑪恩納會(huì)進(jìn)入暖機(jī)狀態(tài)，持續(xù)F個(gè)時(shí)刻。暖機(jī)時(shí)間結(jié)束后，可以繼續(xù)選擇在接下來(lái)的某一時(shí)刻開(kāi)啟技能。
2. 給出 nn個(gè)敵人的在瑪恩納攻擊范圍的起始時(shí)刻和結(jié)束時(shí)刻Li? ,Ri? ，特別的所有敵方單位的生命值 H=R i? ?L i? +1。

開(kāi)始時(shí)刻為第 11 秒，結(jié)束時(shí)刻為第 TT 秒，問(wèn)如何規(guī)劃技能開(kāi)啟時(shí)間可以使瑪恩納最多能殺死多少敵方單位。

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

題解

這題一個(gè)重點(diǎn)就是以時(shí)刻為單位來(lái)看比較好理解，從題意可知是從第1秒開(kāi)始的。

然后遍歷每個(gè)敵人，滿足上圖條件的val[i]的價(jià)值加1,利用差分進(jìn)行優(yōu)化。

再利用前綴和把val數(shù)組求出來(lái)

代碼展示（C++）

#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<

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁(yè)名稱：日暮尋路題解-創(chuàng)新互聯(lián)
文章源于：http://weahome.cn/article/ccohhd.html