自动搬运

查看原文

来自洛谷，原作者为

	mzy2003 **

搬运于2025-08-24 21:55:31，当前版本为作者最后更新于2019-05-10 20:49:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

第一次写题解

emmm。。。

看到这么多红名dalao打的题解，我这个蒟蒻不禁颤抖

本蒟蒻水平有限，看题只是想到了搜索

再一看，可以记忆化

于是有了如下AC代码~~（居然AC了）~~

（还是深搜）

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int map[102][102],f[102][102][11],n,k,a,b,c,an=199999999;
void dfs(int x,int y,int fy,int rs)//横坐标，纵坐标，目前费用，剩余步数 
{
	int add=0;//此步费用 
	if (map[x][y]==-1) return;//边界 
	if (rs<=0||fy>=an) return;//最优性剪枝 
	rs--;
	for (int i=rs;i<=k;i++)//一个剪枝操作：当此坐标剩i（rs（当前剩步）<=i<=k）步时，
	if (f[x][y][i]<=fy) return;//费用还比目前费用少，则可剪枝。（其实可用树状数组logk的，但这儿数据小） 
	f[x][y][rs]=fy;//更新此坐标剩rs步时最小费用（记忆化） 
	if (x==n&&y==n)
	{
		an=min(an,fy);//更新答案 
		return;
	}
	if (map[x][y]==1) add=a,rs=k;//强制加油 
	if (rs==0) add=a+c,rs=k;//没油了，才设站加油 
	dfs(x+1,y,fy+add,rs);
	dfs(x,y+1,fy+add,rs);
	dfs(x-1,y,fy+add+b,rs);
	dfs(x,y-1,fy+add+b,rs);//扩展 
}
int main()
{
	scanf("%d%d%d%d%d",&n,&k,&a,&b,&c);
	for (int i=0;i<=n+1;i++)
	map[0][i]=map[i][0]=map[i][n+1]=map[n+1][i]=-1;//设边界 
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++)
	{
		scanf("%d",&map[i][j]);
		for (int k=0;k<=10;k++)
		f[i][j][k]=99999999;//初始化 
	}
	dfs(1,1,0,k+1);
	printf("%d",an);
	return 0;//好习惯 
}

第一次写，写的不好，请dalao们见谅