鏈接：https://ac.nowcoder.com/acm/contest/318/J
來源：牛客網(wǎng)

題目描述
“無論何時(shí)何地，都會(huì)遵守約定”。“奮力逃吧”。“關(guān)于取下敵人性命這件事，也從不失約”。

小懶蟲zmx平時(shí)最喜歡玩的游戲就是《王者榮耀》，在這款游戲中它也最喜歡百里守約這個(gè)英雄。最近，zmx準(zhǔn)備沖國服百里，所以它開始練英雄，你有很多個(gè)時(shí)間段來練習(xí)英雄，每個(gè)時(shí)間段有一個(gè)開始時(shí)間點(diǎn)和結(jié)束時(shí)間點(diǎn)，以及可以獲得的熟練度。不過現(xiàn)在你可以隨意修改任意練習(xí)時(shí)間段的開始和結(jié)束時(shí)間點(diǎn)，但是你不能修改時(shí)間段的長度和獲得的熟練度！由于要學(xué)習(xí)，你只能在固定時(shí)間段玩游戲，問你最多可以獲得多少熟練度？

例如：你可以把[2,3），修改為[1,2）或者[3,4）等等，他們的長度都是1。

注意：對于某個(gè)時(shí)間段，不管你有沒有修改，必須練完整個(gè)時(shí)間段長度才能獲得熟練度！

輸入描述:
第一行，三個(gè)整數(shù)n,S,T(0<n<=1000,0<S<T<1000)代表n個(gè)時(shí)間段和你能在[S,T）時(shí)間段內(nèi)玩游戲。

接下來n行，每行三個(gè)整數(shù)a,b(0<a<b<1000),c(0<c<1e7)，用空格分開，代表時(shí)間段起始時(shí)間[a,b）和可以獲得的熟練度。
輸出描述:
輸出一行，包括一個(gè)整數(shù)，表示zmx能獲得的最大熟練度。
示例1
輸入
復(fù)制
3 1 3
1 3 5
2 4 6
4 7 8
輸出
復(fù)制
6
示例2
輸入
復(fù)制
5 1 5
1 2 1
2 3 2
1 3 3
3 4 2
3 6 4
輸出
復(fù)制
7

題目描述的很牛逼。唉，最后還是沒有想到那一點(diǎn)。。
我們把總的時(shí)間容量看成背包，每一個(gè)的時(shí)間看做體積和重量。典型的01背包。唉
代碼如下：

#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std;const int maxx=1e3+10; ll dp[maxx]; int w[maxx]; int v[maxx]; int n,l,r;int main() {scanf("%d%d%d",&n,&l,&r);ll sum=r-l;for(int i=0;i<n;i++){int s,e;scanf("%d%d%d",&s,&e,&v[i]);w[i]=e-s;}for(int i=0;i<n;i++)for(int j=sum;j>=w[i];j--){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}cout<<dp[sum]<<endl; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的王者荣耀（01背包）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。