42wa 禁食后人
查看原帖
42wa 禁食后人
800186
jur10n楼主2025/2/7 15:42

rt,如下

for(int k=1;k<=m+n;k++){
		//禁食后人!!!
		//其实直接用n就可以的
		//如果要用min n,k 需要把k+1!!!!!!
		//因为会漏掉初始情况(少走一个),参考下面的k-j+1
		
		for(int i=1;i<=min(n,k+1);i++){//重复点的处理:我们可以这样想,2条路径不相交,那么肯定一条在上面,一条在下面;随便画2条路径就可以看出来了,由此来处理重复点
			for(int j=i+1;j<=min(n,k+1);j++){
				if(i!=j){
					f[k][i][j]=Getmax(i,j,k) + s[k-i+1][i] + s[k-j+1][j];//画个图数数点 需要+1
				}
			}
		}
	}
	
	//dp完了以后,发现dp到了左下角的上面和左面,看看那个最大就可以了
	//遍历不到n,m的原因可以看看k-i+1的计算方法
	f[n+m][n][n]=max(f[n+m-1][n][n-1],f[n+m-1][n-1][n]);
	cout<<f[n+m][n][n];
2025/2/7 15:42
加载中...