24分求助!!!
查看原帖
24分求助!!!
362325
_YUZIhaizhao_楼主2021/8/31 15:56

这道题为什么24分?

嘤嘤嘤蒟蒻呻吟。

恳请大佬指点

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,k,m,b,c,ans=0x3f3f3f3f;
int f[110][110][11];
int a[110][110],sum;
int tot=0x3f3f3f3f;
//x:横坐标 y:纵坐标 u:步数 stemp:最小费用
void dfs(int x,int y,int u,int stemp)
{
	int sum=0;
	//cout<<stemp<<" ";
	if(a[x][y]==-1)
	    return;
	if(u<=0||stemp>=tot)
	    return;
    u--;
    for(int i=u;i<=k;i++)
        if(f[x][y][i]<=stemp)
            return;
    f[x][y][u]=stemp;
    if(x==n&&y==n)
	{
	    ans=min(ans,stemp);
		return;
	}
    if(a[x][y]==1)  sum+=m,u=k;
    if(u==0)     sum+=c,u=k;
    dfs(x+1,y,u,stemp+sum);
    dfs(x,y+1,u,stemp+sum);
    dfs(x-1,y,u,stemp+b+sum);
    dfs(x,y-1,u,stemp+b+sum);
}
int main()
{
    scanf("%d%d%d%d%d",&n,&k,&m,&b,&c);
    for(int i=0;i<=n+1;i++)
        a[0][i]=a[i][0]=a[i][n+1]=a[n+1][i]=-1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
            for(int l=0;l<=10;l++)
                f[i][j][l]=0x3f3f3f3f;
        }
    dfs(1,1,k+1,0);
    cout<<ans;
}
2021/8/31 15:56
加载中...