题解 P6249 【神帖】

这道题目我一看到就想起了经典题——关路灯

但是时间好像不太好搞啊！

我们可以枚举时间qwq

考虑 \(4\) 维 \(dp\) \(f_{i,j,t,0/1}\) 表示 \(zrl\) 看了第 \(i\) 页到第 \(j\) 页，此时时间为 \(t\)。

最后一维

如果是 \(0\) 就是在第 \(i\) 页。
如果是 \(1\) 就是在第 \(j\) 页。

为什么这样是对的？

我们会发现，首先为了最优 \(zrl\) 绝对不会刻意地去浪费时间，像这样

要往左走，一定会超过之前走到最左的点

要往右走，一定会超过之前走到最右的点

所以，我们可以开始转移了。

按照上面的结论 \(f_{i,j,t,1}\) 有 \(2\) 种可能
- 一种是 \(f_{i+1,j,t-(a_{i+1}-a_i),0}\)
- 一种是 \(f_{i+1,j,t-(a_j-a_i),1}\)
按照上面的结论 \(f_{i,j,t,0}\) 有 \(2\) 种可能
- 一种是 \(f_{i,j-1,t-(a_j-a_{j-1}),1}\)
- 一种是 \(f_{i,j-1,t-(a_j-a_i),0}\)

代码就很好写了：

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

}

巴特西

题解 P6249 【神帖】

最新文章

热门文章