CF Round #446 改题

在机房vp了一番div1，~~就做了一个题，~~ 于是这篇文章就用来改题了。
链接：Here

A

题目：给定一个数列$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;
}

B

题目：给定$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;
}

# 概率期望dp, 线段树, 高斯消元

CF Round #446 改题

A

B

评论

分类

Your browser is out-of-date!