10.27T2 线性DP+拆分

2.树塔

(tower)

【问题描述】

相信大家都在长训班学过树塔问题，题目很简单求最大化一个三角形数塔从上往下走的路径和。走的规则是：（i，j）号点只能走向（i+1，j）或者（i+1，j+1）。如下图是一个数塔，映射到该数塔上行走的规则为：从左上角的点开始，向下走或向右下走直到最底层结束。
   1
  3 8
  2 5 0
  1 4 3 8
  1 4 2 5 0
   路径最大和是1+8+5+4+4 = 22，1+8+5+3+5 = 22或者1+8+0+8+5 = 22。
   小S觉得这个问题so easy。于是他提高了点难度，他每次ban掉一个点（即规定哪个点不能经过），然后询问你不走该点的最大路径和。
  当然他上一个询问被ban掉的点过一个询问会恢复（即每次他在原图的基础上ban掉一个点，而不是永久化的修改）。

【输入】

第一行包括两个正整数N，M，分别表示数塔的高和询问次数。
  以下N行，第i行包括用空格隔开的i-1个数，描述一个高为N的数塔。
  而后M行，每行包括两个数X，Y，表示第X行第Y列的数塔上的点被小S ban掉，无法通行。
  由于读入数据较大，c或c++请使用较为快速的读入方式。

【输出】

M行每行包括一个非负整数，表示在原图的基础上ban掉一个点后的最大路径和，如果被ban掉后不存在任意一条路径，则输出-1。

【输入输出样例】

tower.in	tower.out
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 0
1+3+5+4+4 = 17 或者 1+3+5+3+5=17
第二次：
1
3 8
2 5 0
1 4 3 8
1 4 2 X 0
1+8+5+4+4 = 22
第三次：你们都懂的！无法通行，-1！

【数据规模和约定】

所有测试数据范围和特点如下：

对于所有数据，数塔中的数X的大小满足0≤X≤10⁶

 

测试点编号	N	M	特殊约定
1	≤ 5	≤ 3
2
3		≤ 105
4
5	≤ 50	≤ 103	满足点(i,j)上的数=i*j
6
7
8
9	≤ 300	≤ 104	数塔中所有数相等
10
11
12
13	≤ 1000	≤ 3*105	满足点(i,j)上的数=i-j
14			满足点(i,j)上的数=i*j
15			数塔中所有数相等
16
17
18		5*105	满足点(i,j)上的数=i-j
19
20

 

 

 

 

 

这题我SB了，本应想到前后缀DP是可行的，但是我一直卡在去掉数字的影响导致65pt

考虑求出每一个位置从上到下的最大值和从小到大的最大值，枚举去掉的那一行的前后缀和的最大值就可以了

暴力其实可以拿80但是我分段分的不好

code：

1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 long long a[1005][1005],suf[1005][1005],pre[1005][1005]; 5 long long read(){ 6 long long x=0,f=1;char c=getchar(); 7 while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} 8 while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();} 9 return x*f; 10 } 11 int main() { 12 long long n,m; 13 n=read(),m=read(); 14 for(long long i=1; i<=n; i++) 15 for(long long j=1; j<=i; j++) 16 a[i][j]=read(),suf[i][j]=max(suf[i-1][j],suf[i-1][j-1])+a[i][j]; 17 for(long long i=n; i>=1; i--) 18 for(long long j=1; j<=i; j++) 19 pre[i][j]=max(pre[i+1][j],pre[i+1][j+1])+a[i][j]; 20 for(long long i=1; i<=m; i++) { 21 long long x=read(),y=read(),max0=0; 22 if(x==1&&y==1) {cout<<-1<<'\n';continue;} 23 for(long long j=1; j<=x; j++) { 24 if(j==y)continue; 25 max0=max(max0,pre[x][j]+suf[x][j]-a[x][j]); 26 } 27 cout<<max0<<'\n'; 28 } 29 return 0; 30 }

over

转载于:https://www.cnblogs.com/saionjisekai/p/9860926.html

总结

以上是生活随笔为你收集整理的10.27T2 线性DP+拆分的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。