社区讨论
WA 42pts 禁食后人
P1004[NOIP 2000 提高组] 方格取数参与者 5已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @m6ugqv9g
- 此快照首次捕获于
- 2025/02/07 15:46 去年
- 此快照最后确认于
- 2025/11/04 09:49 4 个月前
rt,这题跟传纸条不太一样的是它的起点终点都能有数值,所以注意你dp的范围,不要忘记了首尾的值
CPPfor(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];
回复
共 4 条回复,欢迎继续交流。
正在加载回复...