Codeforces 351C Jeff and Brackets 矩阵优化DP

约定不等于承诺〃 2021-12-12 02:01 396阅读 0赞

题意:你要在纸上画一个长度为n * m的括号序列,第i个位置画左括号的花费是a[i % n], 画右括号的花费是b[i % n],问画完这个括号序列的最小花费。n <= 20, m <= 1e7

思路:如果不管n和m的限制,这个题很好做,设dp[i][j]是到i位置,平衡因子是j的花费,dp[i][j] = min(dp[i - 1][j - 1] + a[i], dp[i - 1][j + 1] + b[i]),但是这样n * m到2e8级别,这是我们无法承受的。不过,我们可以发现一个性质:平衡因子的大小不会超过2 * n,因为如果超过2 * n,我们可以通过交换顺序而不改变答案,让平衡因子都小于2 * n。我们想一下dp的转移,我们发现可以用一次矩阵乘法来执行一次转移(设转移矩阵是C),那么C[j][j + 1] = a[i],C[j][j - 1] = b[i],那么乘一次这个矩阵就执行了一次转移,因为a和b数组是长度为n的循环,那么我们可以一次处理出n次转移的矩阵(由矩阵乘法的结合律可知),再用矩阵快速幂执行这样的n次转移m次,就得到了最终的答案。

代码:

  1. #include <bits/stdc++.h>
  2. #define INF 2e9
  3. #define LL long long
  4. using namespace std;
  5. int a[30], b[30], N;
  6. struct Matrix {
  7. LL a[55][55];
  8. Matrix(int x = INF) {
  9. memset(a, 0x3f, sizeof(a));
  10. for (int i = 0; i < N; i++)
  11. a[i][i] = x;
  12. }
  13. friend Matrix operator * (const Matrix& A, const Matrix& B) {
  14. Matrix ans;
  15. for (int i = 0; i < N; i++)
  16. for (int j = 0; j < N; j++)
  17. for (int k = 0; k < N; k++)
  18. ans[i][j] = min(ans[i][j], A[i][k] + B[k][j]);
  19. return ans;
  20. }
  21. Matrix operator ^ (int y) {
  22. Matrix x = *this, ans(0);
  23. for (; y; y >>= 1) {
  24. if(y & 1) ans = ans * x;
  25. x = x * x;
  26. }
  27. return ans;
  28. }
  29. LL*operator [](int x) {
  30. return a[x];
  31. }
  32. const LL*operator [](int x) const {
  33. return a[x];
  34. }
  35. };
  36. int main() {
  37. int n, m;
  38. scanf("%d%d", &n, &m);
  39. for (int i = 1; i <= n; i++)
  40. scanf("%d", &a[i]);
  41. for (int i = 1; i <= n; i++)
  42. scanf("%d", &b[i]);
  43. N = 2 * n + 1;
  44. Matrix dp, A(0);
  45. dp[0][0] = 0;
  46. for (int i = 1; i <= n; i++) {
  47. Matrix tmp;
  48. for (int j = 0; j <= N; j++) {
  49. if(j) tmp[j - 1][j] = a[i];
  50. if(j < 2 * n) tmp[j + 1][j] = b[i];
  51. }
  52. A = A * tmp;
  53. }
  54. dp = dp * (A ^ m);
  55. printf("%lld\n", dp[0][0]);
  56. }

  

转载于:https://www.cnblogs.com/pkgunboat/p/10990308.html

发表评论

表情:
评论列表 (有 0 条评论,396人围观)

还没有评论,来说两句吧...

相关阅读