有大佬能告诉我为什么有条语句位置不同,答案就不正确了
查看原帖
有大佬能告诉我为什么有条语句位置不同,答案就不正确了
1332997
sdjyyds楼主2024/5/3 15:46
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010,M = 25;

typedef long long LL;
const LL INF = 1e18;
//f[i][j][k]表示到达高度为i,长度为j,跳跃的次数为k的最大值
//状态更新 跑时 i == 1 f[1][j][k] = max(f[1][j + 1][k])
//向上跳跃时,更新向上跳后最高位置x,y,加上经过各个点的值sum,f[i][j][k] = max(f[i][j][k],dfs(x,y,k + 1) + sum);
//下落时  f[i][j][k] = max(f[i][j][k],dfs(i - 1,j + 1,k));
 
LL f[M][N][6],res = -INF,res1,res2;
int a[M][N],n,m,pay1,pay2;
int jc,jh;

LL  dfs(int x,int y,int num)
{
	if(y > n) return 0;
	if(a[x][y] == -1) return -INF;
	if(f[x][y][num] != -1) return f[x][y][num];
	if(x == 1) num = 0;
	LL ans = -INF,sum = 0;bool flag = 1;
	//此行有毒,放在这里有一个数据TLE 
	//if(x == 1) ans = max(ans,dfs(x,y + 1,0));
	//向上跳
	if(num < jc)
	{
		int i;
		for(i = 1; i < jh; i++)
		{
			if(a[x + i][y + i] == -1)
			{
				flag = 0;
				break;
			}
			sum += a[x + i][y + i];
		}
		if(flag) ans = max(ans,sum + dfs(x + jh,y + jh,num + 1));
	} 
	if(x == 1) ans = max(ans,dfs(x,y + 1,0));
	if(x > 1) ans = max(ans,dfs(x - 1, y + 1,num));
	f[x][y][num] = ans + a[x][y];
	return f[x][y][num];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n >> m >> pay1 >> pay2;
	
	for(int i = 1; i <= m; i++)
		for(int j = 1; j <= n; j++) cin >> a[i][j];
		
	for(jc = 1; jc <= 5; jc++)
		for(jh = 1; jh * jc < m; jh++)
		{
			memset(f,-1,sizeof f);
			LL temp = dfs(1,0,m) -(jh - 1) * pay1 - (jc - 1) * pay2;	
			if(temp > res) res = temp,res1 = jh,res2 = jc;		
		}
	if(res > 0) cout << res << " " << res2 << " " << res1; 
	else cout << "mission failed";
	 
	return 0; 
}
2024/5/3 15:46
加载中...