Salve, sto provando a risolvere questo problema in dp ed essenzialmente il mio ragionamento è di guardare per ogni valore i risultati intermedi dei precedenti e qualora il valore sia divisibile con un valore precedente o viceversa prendere la soluzione migliore fino a questo punto. Però faccio solo il primo testcase e non riesco a trovare input per cui non funzioni. Per esempio non so se il testo accetta un numero come coppia con se stesso ma anche facendo questa modifica non risolvo. Qualche idea?
#include <bits/stdc++.h>
using namespace std;
int main()
{
ifstream fin ("input.txt");
ofstream fout ("output.txt");
fin.tie(0);
fin.sync_with_stdio(0);
fout.tie(0);
fout.sync_with_stdio(0);
int n;
fin >> n;
vector<int> v(n);
for(int &i:v)
{
fin>>i;
}
vector<int> dp(n,1);
int longest = 1;
for(int i = 1; i < n; i++)
{
for(int j = 0; j < i; j++)
{
if(v[i] % v[j] == 0 || v[j] % v[i] == 0)
{
dp[i] = max(dp[i], dp[j]+1);
}
}
longest = max(dp[i], longest);
}
fout << longest;
return 0;
}