[jzoj 5770]【2018提高组模拟A组8.6】可爱精灵宝贝 (区间dp)

Description

Branimirko是一个对可爱精灵宝贝十分痴迷的玩家。最近，他闲得没事组织了一场捉精灵的游戏。游戏在一条街道上举行，街道上一侧有一排房子，从左到右房子标号由1到n。

刚开始玩家在k号房子前。有m个精灵，第i只精灵在第A[i]栋房子前，分值是B[i]，以及它在T[i]秒内（含）存在，之后消失。Branimirko可以选择移动至相邻的房子，耗时1秒。抓住精灵不需要时间，精灵被抓住后消失。时间从第1秒开始。Branimirko能最多获得多少分值和。

Input

输入的第1行为三个正整数n，k，m。

接下来m行描述精灵的信息，分别为A[i]，B[i]，T[i]。

Output

输出Branimirko能最多获得多少分值和。

Sample Input

10 5 4

1 30 4

3 5 7

7 10 12

9 100 23

Sample Output

115

Data Constraint

20%的数据：m≤10

40%的数据：m≤20

k≤n≤1000,m≤100,A[i] ≤N,B[i] ≤100,T[i] ≤2000，所有数为正整数。

Hint

很遗憾，它恰好不能抓住在一号房子前的精灵。

如果T[1]改成5，答案就是145

Solution

设f[l][r][k]表示已经抓了l~r区间第k秒在左端点 g[l][r][k]在右端点

那么考虑四种情况转移到f[l][r][k]或g[l][r][k]

f(l+1,r)->f(l,r)

g(l+1,r)->f(l,r)

f(l,r-1)->g(l,r)

g(l,r-1)->g(l,r)

Code

//By Menteur_Hxy

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define M(a,b) memset(a,(b),sizeof(a))

#define F(i,a,b) for(i=(a);i<=(b);i++)

using namespace std;

int read() {

	int x=0,f=1; char c=getchar();

	while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}

	while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();

	return x*f;

}

const int N=1010,M=110,T=2010;

int n,K,m,ans,INF;

int f[M][M][T],g[M][M][T],pl[M],da[M],en[M],val[T][N],vis[N],fla[N],id[M];

bool cmp(int x,int y) {return pl[x]<pl[y];}

void print(int l,int r,int t) {

	printf("f[%d][%d][%d]=%d\n",l,r,t,f[l][r][t]);

	printf("g[%d][%d][%d]=%d\n",l,r,t,g[l][r][t]);

}

signed main() {

	freopen("go.in","r",stdin);

	freopen("go.out","w",stdout);

	n=read(),K=read(),m=read(); int i,j,k,l=0,r=0,tim;

	F(i,1,m) pl[i]=read(),da[i]=read(),en[i]=read(),vis[pl[i]]=1,id[i]=i;

	sort(id+1,id+1+m,cmp);

	F(i,1,m) {

		if(pl[id[i]]<=K&&en[id[i]]>=K-pl[id[i]]+1) l=id[i];

		if(pl[id[i]]>K&&en[id[i]]>=pl[id[i]]-K+1) {r=id[i];break;}

	}

	if(l) f[l][l][K-pl[l]+1]=g[l][l][K-pl[l]+1]=da[l];

	if(r) f[r][r][pl[r]-K+1]=g[r][r][pl[r]-K+1]=da[r];

//	printf("f[%d][%d][%d]=%d\n",l,l,K-pl[l]+1,f[l][l][K-pl[l]+1]);

//	printf("f[%d][%d][%d]=%d\n",r,r,pl[r]-K+1,f[r][r][pl[r]-K+1]);

//	if(!ans) return puts("0"),0;

	F(k,1,2000) {

		F(i,1,m) F(j,i+1,m) {

			l=id[i],r=id[j];

			if(k>=(tim=pl[id[l+1]]-pl[l])&&f[id[l+1]][r][k-tim]) {

				if(en[l]>=k) f[l][r][k]=max(f[l][r][k],f[id[l+1]][r][k-tim]+da[l]);

				else f[l][r][k]=max(f[l][r][k],f[id[l+1]][r][k-tim]);

			}

			if(k>=(tim=pl[r]-pl[id[r-1]])&&g[l][id[r-1]][k-tim]) {

				if(en[r]>=k) g[l][r][k]=max(g[l][r][k],g[l][id[r-1]][k-tim]+da[r]);

				else g[l][r][k]=max(g[l][r][k],g[l][id[r-1]][k-tim]);

			}

			if(k>=(tim=pl[r]-pl[l])&&g[id[l+1]][r][k-tim]) {

				if(en[l]>=k) f[l][r][k]=max(f[l][r][k],g[id[l+1]][r][k-tim]+da[l]);

				else f[l][r][k]=max(f[l][r][k],g[id[l+1]][r][k-tim]);

			}

			if(k>=(tim=pl[r]-pl[l])&&f[l][id[r-1]][k-tim]) {

				if(en[r]>=k) g[l][r][k]=max(g[l][r][k],f[l][id[r-1]][k-tim]+da[r]);

				else g[l][r][k]=max(g[l][r][k],f[l][id[r-1]][k-tim]);

			}

//			if(f[l][r][k]||g[l][r][k]) print(l,r,k);

			ans=max(ans,max(f[l][r][k],g[l][r][k]));

		}

	}

	printf("%d",ans);

	return 0;

}

巴特西