刷随机化是真的会上瘾quq

洛谷P3973 [TJOI2015]线性代数

• 看oiwiki上说可以随机化。。。于是。。。
• 就随机在a[i]上选一位取反，然后更新答案，最后输出答案。
• 。。。无话可说
• 代码：
  

   1 #include <bits/stdc++.h>
   2 #define nmax 510
   3 //D=(A×B−C)×A的转置 最大  求出一个01矩阵A
   4 using namespace std;
   5 int b[nmax][nmax];
   6 int c[nmax], a[nmax], t[nmax], anst[nmax];
   7 int n, ans=-1e9;
   8 
   9 void upd(){
  10     int newa = 0;
  11     for (int i=1; i<=n; i++) t[i] = 0;
  12     for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) t[i] += b[j][i]*a[j];
  13     for (int i=1; i<=n; i++) t[i] -= c[i];
  14     for (int i=1; i<=n; i++) newa += t[i]*a[i];
  15     ans = max(newa, ans);
  16 }
  17 
  18 int main(){
  19     srand((unsigned)time(NULL));
  20     cin >> n;
  21     for (int i=1; i<=n; i++) {
  22         for (int j=1; j<=n; j++) {
  23             scanf("%d", &b[i][j]);
  24         }
  25     }
  26     for (int i=1; i<=n; i++) scanf("%d", &c[i]);
  27     for (int i=1; i<=n; i++) a[i] = 1;
  28     upd();
  29     for (int i=0; i<1000; i++) {
  30         int p = rand()%n + 1;
  31         a[p] = ( !a[p] );
  32         upd();
  33     }
  34     cout << ans << endl;
  35     return 0;
  36 }

  ??‍??

   

rp算法 随机化 刷题记录

原文：https://www.cnblogs.com/jiecaoer/p/11704024.html