题解 P6249 【神帖】

kradcigam

2020-03-29 11:57:51

Solution

Update 2021.8.4:修改了图1的错误,感谢[___balalida___](https://www.luogu.com.cn/user/237541)! 这道题目我一看到就想起了经典题——[关路灯](https://www.luogu.com.cn/problem/P1220) 但是时间好像不太好搞啊! 我们可以枚举时间qwq 考虑 $4$ 维 $dp$ $f_{i,j,t,0/1}$ 表示 $zrl$ 看了第 $i$ 页到第 $j$ 页,此时时间为 $t$。 最后一维 - 如果是 $0$ 就是在第 $i$ 页。 - 如果是 $1$ 就是在第 $j$ 页。 为什么这样是对的? 我们会发现,首先为了最优 $zrl$ 绝对不会刻意地去浪费时间,像这样 ![360截图18430707839661.jpg](https://i.loli.net/2020/03/29/7CFxNZ5Td934PfQ.jpg) **要往左走,一定会超过之前走到最左的点** **要往右走,一定会超过之前走到最右的点** 所以,我们可以开始转移了。 - 按照上面的结论 $f_{i,j,t,1}$ 有 $2$ 种可能 - 一种是 $f_{i+1,j,t-(a_{i+1}-a_i),0}$ ![8y6AYmiXVOZE3eC.png](https://i.loli.net/2021/08/04/6HMh2qGBZ5cDPk8.png) - 一种是 $f_{i+1,j,t-(a_j-a_i),1}$ ![360截图178606015699100.jpg](https://i.loli.net/2020/03/29/3pXduqao6vD8kcW.jpg) - 按照上面的结论 $f_{i,j,t,0}$ 有 $2$ 种可能 - 一种是 $f_{i,j-1,t-(a_j-a_{j-1}),1}$ ![360截图17860531464236.jpg](https://i.loli.net/2020/03/29/D2pEfsChBbWP65N.jpg) - 一种是 $f_{i,j-1,t-(a_j-a_i),0}$ ![360截图17411024463469.jpg](https://i.loli.net/2020/03/29/8y6AYmiXVOZE3eC.jpg) 代码就很好写了: ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; struct node{ int x,v,t; }a[210]; ll f[210][210][510][2],n,ans;//不开long long见祖宗! bool cmp(node a,node b){ return a.x<b.x; } int work(int x,int y){//算能否get到快乐值 if(a[y].t>=x)return a[y].v; return 0; } int main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].v>>a[i].t; n++;//这里的话,我来解释一下,首先有可能所有帖子的页面都>0或<0,zrl也可能只向左走或只向又走。 sort(a+1,a+n+1,cmp); for(int len=1;len<=n;len++) for(int i=1;i+len<=n;i++){ int j=i+len; if(a[i].x>0||a[j].x<0)continue; int x=min(abs(a[i].x),abs(a[j].x))+a[j].x-a[i].x; for(int t=x;t<=500;t++){ f[i][j][t][0]=max(f[i+1][j][max(t-(a[i+1].x-a[i].x),0)][0],f[i+1][j][max(t-(a[j].x-a[i].x),0)][1] )+work(t,i);//优美的转态转移方程。 f[i][j][t][1]=max(f[i][j-1][max(t-(a[j].x-a[i].x),0)][0],f[i][j-1][max(t-(a[j].x-a[j-1].x),0)][1] )+work(t,j); ans=max(ans,max(f[i][j][t][0],f[i][j][t][1]));//优美的转态转移方程。 } } cout<<ans;//输出 return 0; } ```