Advertisement
Guest User

Untitled

a guest
Jan 17th, 2017
1,668
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.17 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. const int N = 51;
  8. int was[N];
  9. int cur[N];
  10. int a[N];
  11. int lul[N];
  12. int dp[N];
  13. double temp = 1;
  14. double t0 = 1e9;
  15.  
  16. int main()
  17. {
  18. #ifdef ONPC
  19.     freopen("a.in", "r", stdin);
  20.     //freopen("a.out", "w", stdout);
  21. #else
  22.     freopen("subrev.in", "r", stdin);
  23.     freopen("subrev.out", "w", stdout);
  24. #endif
  25.     srand(2);
  26.     ios::sync_with_stdio(0);
  27.     int n;
  28.     cin >> n;
  29.     for (int i = 0; i < n; i++)
  30.     {
  31.         lul[i] = rand() % 2;
  32.         cin >> a[i];
  33.     }
  34.     temp = t0;
  35.     int ans = 0;
  36.     int cur = 0;
  37.     while (clock() / (double) CLOCKS_PER_SEC <= 1.99)
  38.     {
  39.         vector <int> p;
  40.         for (int i = 0; i < n; i++)
  41.         {
  42.             was[i] = lul[i];
  43.         }
  44.         for (int it = 0; it < n * temp / t0; it++)
  45.         {
  46.             lul[rand() % n] ^= 1;
  47.         }
  48.         for (int i = 0; i < n; i++)
  49.         {
  50.             if (lul[i])
  51.             {
  52.                 p.push_back(i);
  53.             }
  54.         }
  55.         int t = p.size();
  56.         for (int i = 0; i < t / 2; i++)
  57.         {
  58.             swap(a[p[i]], a[p[t - 1 - i]]);
  59.         }
  60.         int kek = 0;
  61.         for (int i = 0; i < n; i++)
  62.         {
  63.             dp[i] = 1;
  64.             for (int j = 0; j < i; j++)
  65.             {
  66.                 if (a[j] <= a[i])
  67.                 {
  68.                     dp[i] = max(dp[i], dp[j] + 1);
  69.                 }
  70.             }
  71.             kek = max(kek, dp[i]);
  72.         }
  73.         ans = max(ans, kek);
  74.         for (int i = 0; i < t / 2; i++)
  75.         {
  76.             swap(a[p[i]], a[p[t - 1 - i]]);
  77.         }
  78.         if (kek > cur)
  79.         {
  80.             cur = kek;
  81.         }
  82.         else
  83.         {
  84.             double t = exp((kek - cur) / temp);
  85.             int x = 1 + rand();
  86.             int y = 1 + rand();
  87.             x %= y;
  88.             if (x / (double) y <= t)
  89.             {
  90.                 cur = kek;
  91.             }
  92.             else
  93.             {
  94.                 for (int i = 0; i < n; i++)
  95.                 {
  96.                     lul[i] = was[i];
  97.                 }
  98.             }
  99.         }
  100.         temp *= 0.9999;
  101.     }
  102.     cout << ans << '\n';
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement