SHARE
TWEET

Untitled

a guest Jun 18th, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. typedef unsigned long long ull;
  6. typedef pair<int, int> pii;
  7. typedef pair<int, pii> piii;
  8. #define x first
  9. #define y second
  10. void fastInOut();
  11. const double EPS = 1e-8;
  12. const int MOD = 1e9 + 7;
  13. const int N = 1e3 + 5;
  14.  
  15. int n;
  16. int A[N];
  17.  
  18. int dp[N][N];
  19. bool found;
  20. int solve2(int num, int cnt)
  21. {
  22.     if(cnt == 1) {
  23.         found = true;
  24.         return 1;
  25.     }
  26.     int &res = dp[num][cnt];
  27.     if(~res) return res;
  28.     res = 0;
  29.     for(int i=num-1; i>=0; --i) {
  30.         if(A[i] < A[num])
  31.             res = (res % MOD + solve2(i, cnt-1) % MOD) % MOD;
  32.     }
  33.     return res;
  34. }
  35.  
  36. int main()
  37. {
  38.     //freopen("in.txt", "r", stdin);
  39.     //freopen("out.txt", "w", stdout);
  40.     fastInOut();
  41.     int T; cin >> T;
  42.     while(T--) {
  43.         cin >> n;
  44.         for(int i=0; i<=n; i++) {
  45.             for(int j=0; j<=n; j++)
  46.                 dp[i][j] = -1;
  47.         }
  48.         for(int i=0; i<n; i++)
  49.             cin >> A[i];
  50.         found = false;
  51.         for(int i=n; i>=1; i--) {
  52.             int ans = 0;
  53.             for(int j=0; j<n; j++)
  54.                 ans = (ans % MOD + solve2(j, i) % MOD) % MOD;
  55.             if(found) {
  56.                 cout << i << " " << ans << "\n";
  57.                 break;
  58.             }
  59.         }
  60.     }
  61.     return 0;
  62. }
  63.  
  64. void fastInOut(){
  65.     ios_base::sync_with_stdio(0);
  66.     cin.tie(NULL), cout.tie(NULL);
  67. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top