【每日一题】子序列

题意

给定一个由n个元素组成的序列 { a₁, a₂, a₃,..., a_n } ，她想知道其中有多少个子序列 { a_p1, a_p2, ..., a_pm } $(1 ≤ m ≤ n, 1 ≤ p1 < p2 ,..., < pm ≤ n)$ ，满足对于所有的 $i, j$ $(1 ≤ i < j ≤ m)$ , a_pi^pj < a_pj^pi成立。

Solution1

py + dp直接冲。

n, mod = int(input()), int(1000000007)
a = list(map(int, input().split()))
dp = [ 1 for i in range(n) ]
for i in range(0, n):
    for j in range(i):
        if (a[j] ** (i + 1) < a[i] ** (j + 1)):
            dp[i] += dp[j]
print(sum(dp) % mod)

solution2

变形公式。 $a_{i}^{j} < a_{j}^{i} \Leftrightarrow j * log(a_{i}) < i * log(a_{j})$ ，即原题等价于求上升子序列的数量。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll res, dp[105], a[105];
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    dp[i] = 1;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j < i; j++)
      if (j * log(a[i]) > i * log(a[j])) dp[i] = (dp[i] + dp[j]) % mod;
    res = (res + dp[i]) % mod;
  }
  cout << res << '\n';
  return 0;
}