[CSP-S模拟测试]:可爱的精灵宝贝（搜索）

题目描述

$Branimirko$是一个对可爱精灵宝贝十分痴迷的玩家。最近，他闲得没事组织了一场捉精灵的游戏。游戏在一条街道上举行，街道上一侧有一排房子，从左到右房子标号由$1$到$n$。
刚开始玩家在$k$号房子前。有$m$个精灵，第$i$只精灵在第$A_i$栋房子前，分值是$B_i$，以及它在$T_i$秒内（含）存在，之后消失。$Branimirko$可以选择移动至相邻的房子，耗时$1$秒。抓住精灵不需要时间，精灵被抓住后消失。时间从第$1$秒开始。$Branimirko$能最多获得多少分值和。

输入格式

输入的第$1$行为三个正整数$n$，$k$，$m$。
接下来$m$行描述精灵的信息，分别为$A_i$，$B_i$，$T_i$。

输出格式

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

样例

样例输入：

10 5 4
1 30 4
3 5 7
7 10 12
9 100 23

样例输出：

115

数据范围与提示

样例解释：

很遗憾，它恰好不能抓住在一号房子前的精灵。
如果$T_1$改成$5$，答案就是$145$。

数据范围：

$20\%$的数据：$m\leqslant 10$。
$40\%$的数据：$m\leqslant 20$。
$k\leqslant n\leqslant 1000,m\leqslant 100,A_i\leqslant N,B_i\leqslant 100,T_i\leqslant 2,000$，所有数为正整数。

题解

正解是个$DP$，我不会，所以我来打搜索。

首先，我们要明确两点：

　$\alpha.$第一次到的时候就把当前位置的精灵（如果有的话）抓走，肯定不劣。

　$\beta.$如果没有抓到精灵就回头肯定是不优的。

　$\gamma.$如下图中：

　　假设$1,2,3$都有精灵，而我们要去$1$抓精灵，那么可以分解为：先去$2$抓精灵，然后再到$1$抓精灵。

根据如上三条性质，我们的搜索分为两种情况：

　$\alpha.$向左走，抓第一只能抓到的精灵。

　$\beta.$向右走，抓第一只能抓到的精灵。

时间复杂度降低了不少，更是可以通过预处理接着降低时间复杂度。

对比大概是这样子的：

搜索：

正解：

时间复杂度：$\Theta($玄学$)$。

期望得分：$40$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

struct rec{int a,b,t,id;}e[200];

int n,k,m;

int ans;

bool vis[1001],wzc[200];

int minr;

bool cmp(rec a,rec b){return a.a<b.a;}

void dfs(int x,int w,int t)

{

	for(int i=e[x].id;i;i--)

		if(e[i].t>=abs(e[x].a-e[i].a)+t&&!wzc[i])

		{

			wzc[i]=1;

			dfs(e[i].id,w+e[i].b,t+abs(e[x].a-e[i].a));

			wzc[i]=0;

			break;

		}

	for(int i=e[x].id;i<=m;i++)

		if(e[i].t>=abs(e[x].a-e[i].a)+t&&!wzc[i])

		{

			wzc[i]=1;

			dfs(e[i].id,w+e[i].b,t+abs(e[x].a-e[i].a));

			wzc[i]=0;

			break;

		}

	ans=max(ans,w);

}

int main()

{

	scanf("%d%d%d",&n,&k,&m);

	for(int i=1;i<=m;i++)

	{

		scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].t);

		vis[e[i].a]=1;

	}

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

	for(int i=1;i<=m;i++)e[i].id=i;

	for(int i=1;i<=m;i++)if(e[i].a>=k){minr=e[i].id;break;}

	if(!minr){dfs(m,0,abs(e[m].a-k)+1);goto nxt;}

	if(e[minr].a==k)dfs(e[minr].id,0,1);

	else

	{

		dfs(e[minr-1].id,0,abs(e[minr-1].a-k)+1);

		dfs(e[minr].id,0,abs(e[minr].a-k)+1);

	}

	nxt:;

	cout<<ans<<endl;

	return 0;

}

rp++

巴特西