daily 2

two simple DP problems

CF 567C

it is very simple since we just need to calculate the number of ${a[i]/k}$ before a[i] and ${a[i]*k}$ after a[i]
then we multiply them and everything is ok

#define int ll
void solve(){
  int n,k;
  cin>>n>>k;
  vector<int>a(n+1),l(n+1),r(n+1);
  map<int,int>mp;
  for(int i=1;i<=n;++i){
    cin>>a[i];
    if(a[i]%k==0)l[i]=mp[a[i]/k];
    mp[a[i]]++;
  }
  mp.clear();
  int ans=0;
  for(int i=n;i>=1;--i){
    r[i]=mp[a[i]*k];
    ans+=(l[i]*r[i]);
    mp[a[i]]++;
  }
  cout<<ans<<'\n';
  return;
}

CF 566F

simpler, let ${dp[a[i]]}$ means the size of clique with a[i] to be the last object. then we calculate the a[i]*k, and update the answer

void solve(){
  int n;
  cin>>n;
  vector<int>dp(N);
  int ans=0;
  for(int i=1;i<=n;++i){
    int x;
    cin>>x;
    dp[x]++;
    for(int j=2*x;j<N;j+=x){
        dp[j]=max(dp[x],dp[j]);
    }
    ans=max(dp[x],ans);
  }
  cout<<ans<<'\n';
  return;
}