在机房vp了一番div1，就做了一个题， 于是这篇文章就用来改题了。 链接：Here
题目：给定一个数列\(a\)，共\(n\)项，求最多修改一项的值（必须修改成整数）之后数列中最长严格上升子段的最大长度。
显然，修改比不修改要优，起码不会劣于原来的答案。 那么枚举修改哪一项，向两边延申，这部分可以用前缀/后缀和来解决。 注意细节，就做完了。
/** * @Author: Mingyu Li * @Date: 2019-03-26T17:39:28+08:00 * @Last modified by: Mingyu Li * @Last modified time: 2019-03-26T17:42:17+08:00 */ #include <bits/stdc++.h> #define Go(i , x , y) for(register int i = x; i <= y; i++) #define God(i , y , x) for(register int i = y; i >= x; i--) const int N = 100000 + 5; int n , a[N]; int pre[N] , suf[N]; int main() { scanf("%d" , &n); Go(i , 1 , n) scanf("%d" , &a[i]); Go(i , 1 , n) pre[i] = a[i] > a[i - 1] ? pre[i-1] + 1 : 1; God(i , n , 1) suf[i] = (a[i] < a[i + 1]) ? suf[i + 1] + 1 : 1; int max = std::min(2 , n); Go(i , 1 , n) { // for each ai max = std::max(max , pre[i - 1] + 1); max = std::max(max , suf[i + 1] + 1); if(a[i + 1] - a[i - 1] <= 1 && i != n && i != 1) continue; if(i == n) max = std::max(max , pre[i - 1] + 1); else if(i == 1) max = std::max(max , suf[i + 1] + 1); else max = std::max(max , pre[i - 1] + suf[i + 1] + 1); } std::cout << max << std::endl; return 0; }题目：给定\(n\times m\)的矩阵，每次可以将一行或一列所有数\(-p\)，代价是没减之前一行/一列的和。要求做k次，求最大代价。
解法比较有意思。 考虑只能每次消一行/一列怎么做\(\rightarrow\)是可以愉快的优先队列贪心的。 那本质上如果限制了消\(i\)次行，那一定消了\(k-i\)次列。答案就是\(ansrow[i] + anscol[i] + ?\)
\(ansrow\)和\(anscol\)都比较好算，重点在于\(?\)是什么。不难发现，这部分其实就是行列相交的部分，这部分\(p\)都没有被算上，所以\(?=i(k-i)p\).
然后暴力枚举i,就做完了。
/** * @Author: Mingyu Li * @Date: 2019-03-27T18:56:35+08:00 * @Last modified by: Mingyu Li * @Last modified time: 2019-03-27T20:03:55+08:00 */ #include <bits/stdc++.h> #define int long long #define Go(i , x , y) for(register int i = x; i <= y; i++) #define God(i , y , x) for(register int i = y; i >= x; i--) const int N = 1000 + 10; int n , m , a[N][N] , k , p , ansrow[N*N] , anscol[N*N]; std::priority_queue <int> q1; signed main() { scanf("%I64d%I64d%I64d%I64d" , &n , &m , &k , &p); Go(i , 1 , n) Go(j , 1 , m) scanf("%I64d" , &a[i][j]); Go(i , 1 , n) { int sum = 0; Go(j , 1 , m) sum += a[i][j]; q1.push(sum); } Go(i , 1 , k) { int x = q1.top(); q1.pop(); ansrow[i] = ansrow[i - 1] + x; q1.push(x - m * p); } while(!q1.empty()) q1.pop(); Go(j , 1 , m) { int sum = 0; Go(i , 1 , n) sum += a[i][j]; q1.push(sum); } Go(i , 1 , k) { int x = q1.top(); q1.pop(); anscol[i] = anscol[i - 1] + x; q1.push(x - n * p); } int ans = LLONG_MIN; Go(i , 0 , k) { int a = i , b = k - i; int total = a * b * p; ans = std::max(ans , ansrow[i] + anscol[k - i] - total); } std::cout << ans << std::endl; return 0; }转载于:https://www.cnblogs.com/LiM-817/p/10887255.html
相关资源：数据结构—成绩单生成器