华丽转身

在红星中学，一个年级一学年共有 n 场考试，每场考试都有 m 名同学参加，有一个巨佬叫李华，他已经不屑于通过AK考试来获得快感，于是他找到了一些另类的方法。
众所周知，班主任在每次考试后都会为相对上次考试排名进步了 $50\%$ （向下取整，eg：上次获得了第 5 名获得 $\leq2$ 的排名即可获得华丽转身奖）的同学颁发华丽转身奖，在i场考试中获得华丽转身奖可以获得 $num_i$ 份奖品（特别的，第一次考试不能获得华丽转身奖）。
而由于班主任不同时期的财政状况不同，所以每一次考试华丽转身奖的奖品份数也不尽相同。
因为李华太强了，他在每场考试中可以精准控制他的排名在 $[l_i,r_i]$ 内，他想最大化获得奖品的份数，他在 1s 中内就算出了答案，现在想考考你！

第一行输入两个正整数 n,m ，分别表示考试的场数和参加考试的人数
接下来 n 行每行输入 3 个数 $l_i,r_i,num_i$ ，表示第 i 场考试可以控制的排名区间为 $[l_i,r_i]$ ,且若满足条件即可获得 $num_i$ 份奖品( $1\leq l_i \leq r_i \leq m$ )

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; int n;ll m; ll dp[N]; ll lft[N],rgt[N],num[N]; int main(){ int i,j; cin>>n>>m; for(i=1;i<=n;i++) cin>>lft[i]>>rgt[i]>>num[i]; for(i=2;i<=n;i++){ ll sum=0,last=0; for(j=i;j>=1;j--){ last=max(last*2,lft[j]); if(last>rgt[j]) break; dp[i]=max(dp[i],dp[j-1]+sum); sum+=num[j]; } } cout<<dp[n]; return 0; }

详情