贵州省住房和城乡建设厅网站首页,教育网站开发,网站型营销,百度收录查询接口树塔狂想曲
题目大意#xff1a;
有一个数字金字塔#xff0c;让你求出去掉一个点后#xff0c;从最顶端走到最低端的最大值#xff08;只能往下或右下走#xff09;
原题:
题目描述
相信大家都在长训班学过树塔问题#xff0c;题目很简单求最大化一个三角形数塔从上…树塔狂想曲
题目大意
有一个数字金字塔让你求出去掉一个点后从最顶端走到最低端的最大值只能往下或右下走
原题:
题目描述
相信大家都在长训班学过树塔问题题目很简单求最大化一个三角形数塔从上往下走的路径和。走的规则是ij号点只能走向i1j或者i1j1。如下图是一个数塔映射到该数塔上行走的规则为从左上角的点开始向下走或向右下走直到最底层结束。
1 3 8 2 5 0 1 4 3 8 1 4 2 5 0
路径最大和是18544 2218535 22或者18085 22。 小S觉得这个问题so easy。于是他提高了点难度他每次ban掉一个点即规定哪个点不能经过然后询问你不走该点的最大路径和。 当然他上一个询问被ban掉的点过一个询问会恢复即每次他在原图的基础上ban掉一个点而不是永久化的修改。
输入
第一行包括两个正整数NM分别表示数塔的高和询问次数。 以下N行第i行包括用空格隔开的i - 1个数描述一个高为N的数塔。 而后M行每行包括两个数XY表示第X行第Y列的数塔上的点被小S ban掉无法通行。 由于读入数据较大c或c请使用较为快速的读入方式
输出
M行每行包括一个非负整数表示在原图的基础上ban掉一个点后的最大路径和如果被ban掉后不存在任意一条路径则输出-1。
输入样例
5 3
1
3 8
2 5 0
1 4 3 8
1 4 2 5 0
2 2
5 4
1 1输出样例
17
22
-1说明
【样例解释】
第一次是
1
3 X
2 5 0
1 4 3 8
1 4 2 5 013544 17 或者 1353517 第二次
1
3 8
2 5 0
1 4 3 8
1 4 2 X 018544 22 第三次你们都懂的无法通行-1
解题思路
很明显 直接暴力是不可能的我们先预处理出来从起点到某个点的最大值和从某个点到终点的最大值然后就可以求出经过某个点的最大值然后就可以求出某一行的最大值和次大值 然后入过经过输入的点是最大值那说明不能走那走次大的否则走最大的
代码
#includecstdio
#includecstring
#includeiostream
using namespace std;
int n,m,xx,yy,num,a[1005][1005],f[1005][1005];
int df[1005][1005],ff[1005][1005],ans[1005],ans1[1005];
int read()//快读
{char xgetchar();int d1,l0;while (x0||x9) {if (x-) d-1;xgetchar();}while (x0x9) l(l3)(l1)x-48,xgetchar();return l*d;
}
void writ(int c) {if (c9) writ(c/10); putchar(c%1048); return;}
void write(int s) {s0?putchar(45),writ(-s):writ(s); putchar(10); return;}
int main()
{nread();mread();for (int i1;in;i)for (int j1;ji;j){a[i][j]read();f[i][j]max(f[i-1][j],f[i-1][j-1])a[i][j];//预处理}for (int in;i0;--i)for (int j1;ji;j)df[i][j]max(df[i1][j],df[i1][j1])a[i][j];for (int i1;in;i){for (int j1;ji;j){ff[i][j]max(f[i-1][j],f[i-1][j-1])max(df[i1][j],df[i1][j1])a[i][j];//计算if (ff[i][j]ans[i]) ans[i]ff[i][j],numj;//求最大的}for (int j1;ji;j)if (j!num)ans1[i]max(ans1[i],ff[i][j]);//求次大的}for (int i1;im;i){xxread();yyread();if (xx1yy1) putchar(45),putchar(49),putchar(10);//无法到达else if (ff[xx][yy]ans[xx]) write(ans1[xx]);//次大else write(ans[xx]);//最大}
}
