2.13-?训练题解 记录不会的或者WA的地方 待填

DZY Loves Sequences

传送门：446A
题意：给一个长度为n的数列，求一个子段，最多改变当中的一个值，使得子段为严格单调增，求子段的最大长度。
求解：最长上升子序列就是一个简单dp

1
2
3
4
if(a[i]>a[i-1])
  {
   b[i]=b[i-1]+1;
  }

一开始的想法是遍历一遍，遇到b[i]==1先判断一下前后两段能不能接起来，如果可以就在原来的基础上+1.
这样写的问题是，没法控制只加一次，本质上就是贪心想法错了。
后来的改进是不从头开始遍历，当成一段一段处理，记录上一段的长度，然后假设可以接起来，每一段都判断一下，最后求最大值。
还遇到的问题是：
1.最后一段的处理在循环的外面，要记得最后写一下。
2.如果每一段都不能接起来，那就是最长上升子序列的长度+1。
3.需要判断两段可以接起来的长度与最长上升子序列的长度+1哪个更大
4.存在原数列就是严格单调增的情况，这样答案就是原数列的长度。

DZY Loves Modification

传送门：446B
题意：输入一个n*m的矩阵，k值和p值，对一个矩阵进行恰好k次操作，k操作有两种选择：1.选择矩阵的某行并将行的每个元素减少p。此操作带来快乐值，该值等于减少前行元素的总和。2.选择矩阵的某列并将列的每个元素减少p。此操作带来快乐值，该值等于减少前行元素的总和。
求可以获得的最大快乐总价值
求解：行和列是相互影响的，所以不能用两个优先队列最大的来贪心。
能够发现，其实先选行，再选列与先选列，再选行没有任何区别,选i行，k-i列，最后都是-p*i*k-i
因此只要枚举选i个行，k-i个列，用优先队列存储一下每次操作之后行/列，最后取最大值即可。
问题：
1.超时！记得加ios::sync_with_stdio(0);cin.tie(0);
2.不开long long见祖宗
3.数组的范围要注意