请使用左闭右开区间
查看原帖
请使用左闭右开区间
773503
Falling_Sakura楼主2023/8/18 09:45

不能写为左闭右闭区间的原因是假如 f[i-1][j] 根本就不存在,它的值是 00,按照左闭右开的写法这样就会导致左端点为 00 从而返回值是 00,这样是正确的,因为不存在根本就无法转移。

而按照左闭右闭的写法的话就会导致明明是 00 却认为这是上个区间的右端点,导致下个区间的左端点变成1,从而返回错误答案。

错误代码:

f[a][i]=i;
......
if(!f[i][j])
	f[i][j]=f[i-1][f[i-1][j]+1];

正确代码:

f[a][i]=i+1;
......
if(!f[i][j])
	f[i][j]=f[i-1][f[i-1][j]];

错误输出:左图。

正确输出:右图。

2023/8/18 09:45
加载中...