jzoj 5770 可爱精灵宝贝

本文主要是介绍jzoj 5770 可爱精灵宝贝，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

这里写图片描述

题解

–是区间dp（好像dfs加神秘玄学剪枝也能过？）
首先，我们可以发现这个人走过的位置是一个区域，而且区域内部的精灵要么被抓，要么消失了（总之就是与以后的转移没有关系）
所以，状态定义：
f[l][r][t] :当这个人走过区间[l,r]，且目前在l处，时间为t时的最大分值
注意，l，r的左右位置要根据大小自己判断

然后我们又发现，现在这个人只有两种方法：左走或右走
他肯定是走到他没有走过的第一个有精灵的房子前，因为他不可能无视他（不符合贪心原则）
所以，转移方程：
看代码，有点长（因为还要判断这个精灵能否抓到）

最后，边界就是：
f[起始房子][起始房子][1]=0

还有可以离散化一下，因为有很多房子前没有精灵，其实是没用的
排一下序，编号放进一个数组就行，k也要放（看成是没有价值，时间为1的精灵）

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN=105;int n,k,m;
int a[MAXN],b[MAXN],t[MAXN];
int w[MAXN];
int maxt;
int f[MAXN][MAXN][2005];
int ans;bool comp(const int &x,const int &y){return a[x]<a[y];
}int main(){freopen("go.in","r",stdin);freopen("go.out","w",stdout);cin>>n>>k>>m;w[0]=0;a[0]=k;b[0]=0;t[0]=1;for(int i=1;i<=m;i++){scanf("%d%d%d",&a[i],&b[i],&t[i]);maxt=max(maxt,t[i]);w[i]=i;}sort(w,w+1+m,comp);memset(f,-1,sizeof(f));for(int i=0;i<=m;i++)if(a[w[i]]==k)f[i][i][1]=0;for(int time=1;time<=maxt;time++){for(int l=0;l<=m;l++){for(int r=0;r<=m;r++){if(f[l][r][time]!=-1){if(l<=r){int T=time+a[w[l]]-a[w[l-1]];if(l>0){if(T<=t[w[l-1]])f[l-1][r][T]=max(f[l-1][r][T],f[l][r][time]+b[w[l-1]]);else f[l-1][r][T]=max(f[l-1][r][T],f[l][r][time]);}T=time+a[w[r+1]]-a[w[l]];if(r<m){if(T<=t[w[r+1]])f[r+1][l][T]=max(f[r+1][l][T],f[l][r][time]+b[w[r+1]]);else f[r+1][l][T]=max(f[r+1][l][T],f[l][r][time]);}}else{int T=time+a[w[l]]-a[w[r-1]];if(r>0){if(T<=t[w[r-1]])f[r-1][l][T]=max(f[r-1][l][T],f[l][r][time]+b[w[r-1]]);elsef[r-1][l][T]=max(f[r-1][l][T],f[l][r][time]);}T=time+a[w[l+1]]-a[w[l]];if(l<m){if(T<=t[w[l+1]])f[l+1][r][T]=max(f[l+1][r][T],f[l][r][time]+b[w[l+1]]);elsef[l+1][r][T]=max(f[l+1][r][T],f[l][r][time]);}}}ans=max(ans,f[l][r][time]);}}}cout<<ans;return 0;
}