Top

(ΦωΦ)<これの答えですよー。目次はここ

---
問4-2
(ΦωΦ)<再帰
#include <iostream>
#include <algorithm>
using namespace std;

int n;
vector<int> a, dp;

// i番目までのLISを求める。
int rec(int i) {
  int &res = dp[i];
  if(res > 0) { return res; }
  // 0番目まで(=要素が1つのとき)のLISは1。
  if(i == 0) { return res = 1; }
  res = 1;
  for(int j=0; j<i; j++) {
    // iより小さいjに対して、j番目までのLISを求めて、
    int x = rec(j);
    // a[j] < a[i]なら、j番目までのLISに1を加える。
    if(a[j] < a[i]) { res = max(res, x+1); }
  }
  return res;
}

int main(void) {
  int q; scanf("%d", &q);
  for(int cases=0; cases<q; cases++) {
    scanf("%d", &n);
    a.assign(n, 0);
    for(int i=0; i<n; i++) { scanf("%d", &a[i]); }
    dp.assign(n, 0);
    rec(n-1);
    int res = *max_element(dp.begin(), dp.end());
    printf("%d\n", res);
  }
  return 0;
}
    

(ΦωΦ)<forループ
#include <iostream>
#include <algorithm>
using namespace std;

vector<int> a, dp;

int main(void) {
  int q; scanf("%d", &q);
  for(int cases=0; cases<q; cases++) {
    int n; scanf("%d", &n);
    a.assign(n, 0);
    for(int i=0; i<n; i++) { scanf("%d", &a[i]); }
    dp.assign(n, 1);
    for(int i=0; i<n; i++) {
      for(int j=0; j<i; j++) {
        if(a[j] >= a[i]) { continue; }
        dp[i] = max(dp[i], dp[j] + 1);
      }
    }
    int res = *max_element(dp.begin(), dp.end());
    printf("%d\n", res);
  }
  return 0;
}
    

(ΦωΦ)<おしまい