Sto provando a risolvere il problema fpb e riesco ad ottenere solamente 49 punti su 100. Non riesco a capire come ottimizzarlo. Sto tentando per il momento di trovare una soluzione efficiente per il caso in cui K=1 (non riesco a superare il subtask 6). Qualche consiglio?. Questo è il mio codice:
#include<bits/stdc++.h>
using namespace std;
ifstream fin("input.txt");
ofstream fout("output.txt");
int main()
{
int n, k;
fin>>n>>k;
vector<long> persone(n);
for(int i=0;i<n;++i)
fin>>persone[i];
vector<vector<long>> res(k+1, vector<long>(n+1));
vector<vector<long>> cont(k+1, vector<long>(n+1));
//inizializzo la prima riga in cui k=1 (caso base)
res[1][1]=persone[0];
cont[1][1]=1;
for(int i=2;i<=n;++i){
int mcdRes=persone[i-1];
res[1][i]=res[1][i-1];
cont[1][i]=cont[1][i-1];
for(int j=i-1;j>=0;--j){
mcdRes=__gcd((int)mcdRes, (int)persone[j]);
res[1][i]=(res[1][i]%1000000007+mcdRes%1000000007)%1000000007;
++cont[1][i];
}
}
//inizializzo i casi in cui n=k
for(int i=2;i<=k;++i){
res[i][i]=(res[i-1][i-1]%1000000007+persone[i-1]%1000000007)%1000000007;
cont[i][i]=1;
}
//computo le altre soluzioni per ogni n e k
for(int i=2;i<=k;++i){
for(int j=i+1;j<=n;++j){
int mcdRes=persone[j-1];
res[i][j]=((res[i][j-1]%1000000007+res[i-1][j-1]%1000000007)%1000000007+(persone[j-1]%1000000007*cont[i-1][j-1]%1000000007)%1000000007)%1000000007;
cont[i][j]=(cont[i][j-1]%1000000007+cont[i-1][j-1]%1000000007)%1000000007;
for(int l=j-2;l>=i-1;--l){
mcdRes=__gcd((int)mcdRes, (int)persone[l]);
res[i][j]=((res[i][j]%1000000007+res[i-1][l]%1000000007)%1000000007+(mcdRes%1000000007*cont[i-1][l]%1000000007)%1000000007)%1000000007;
cont[i][j]=(cont[i][j]%1000000007+cont[i-1][l]%1000000007)%1000000007;
}
}
}
fout<<res[k][n]%1000000007<<"\n";
return 0;
}
Io consiglio di guardare i suggerimenti dati in questo post Fpb(20/100 15 caratteri)( in particolare questo commento Fpb(20/100 15 caratteri)), a me( con molto tempo) sono bastati.
con k==1 ti devi calcolare partendo da un indice x tutti i valori dei suoi sub array per esempio
3
1 2 3
se prendiamo come x l indice 0 dovremmo calcolare il gcd(1),gcd(1,2),gcd(1,2,3);
un approcio comune è quindi la bruteforce di complessità O(N^2) cosa possiamo fare per ridurre questa complessità? Posso raggruppare in qualche modo le soluzioni? cosa puoi sfruttare del gcd per calcolarti piú velocemente le soluzioni? Dato un numero x e un numero y il gcd di x e y che legame avrà con x e y ?
Okey il caso in cui K=1 sono riuscito a risolverlo ora vedo se riesco a risolvere anche per K=2, K=3 ecc… .
Per risolvere il caso in cui K=1 ho precalcolato tutti i divisori degli N numeri, gli ho riordinati in ordine decrescente e poi ho contato i divisori inclusi nella soluzione. Questo è il codice:
int n, k, res=0;
cin>>n>>k;
vector<long> persone(n);
vector<vector<int>> divisor(n, vector<int>());
vector<vector<int>> contDivisor(n, vector<int>());
for(int i=0;i<n;++i)
cin>>persone[i];
//precalcolo tutti i divisori
for(int i=0;i<n;++i){
divisor[i].push_back(1);
divisor[i].push_back(persone[i]);
for(int j=2;j<=sqrt(persone[i]);++j)
if(persone[i]%j==0){
divisor[i].push_back(j);
if(j!=persone[i]/j)
divisor[i].push_back(persone[i]/j);
}
contDivisor[i].resize(divisor[i].size(), 0);
}
//gli riordino in ordine decrescente
for(int i=0;i<n;++i)
sort(divisor[i].rbegin(), divisor[i].rend());
for(int i=0;i<n;++i)
contDivisor[i][0]=1;
for(int i=0;i<n-1;++i)
for(int j=0;j<divisor[i].size();++j)
if(contDivisor[i][j]!=0)
for(int k=0;k<divisor[i+1].size();++k)
if(divisor[i][j]%divisor[i+1][k]==0){
contDivisor[i+1][k]=contDivisor[i+1][k]+contDivisor[i][j];
break;
}
//calcolo la soluzione
for(int i=0;i<n;++i)
for(int j=0;j<divisor[i].size();++j)
res=res+(divisor[i][j]*contDivisor[i][j]);
cout<<res<<"\n";
Ho pensato un po’ a come risolvere anche per gli altri K, ma non mi vengono in mente idee. Penso che non sia possibile risolverlo utilizzando la matrice NxK, ma bisogni definire i sottoproblemi diversamente. Qualche hint?
Non ho proprio idea di come fare qualcuno potrebbe darmi qualche consiglio per favore?