Salut !! Am incercat sa rezolv urmatoarea problema : http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=683 (http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=683)
Am rezolvat problema prin programare dinamica ,dar nu stiu de ce iau 90.Am retinut toate cifrele care apar in numerele citite in ordine in sirul v dupa care am facut dinamica pentru a afla suma maxima pt. un prefix de lungime 1,2,3 ... , L.Am retinut doar 4 linii in matrice.Problema e ca iau WA pe ultimul test si nu vad ce caz as fi putut uita. ](*,)
Ma poate ajuta cineva ?
Multumesc.
Sursa mea:
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 2000
long S[4][maxn],nou;
int v[maxn],n,L;
char snr[16],sir[maxn];
int main(){
int i,j;
freopen("suma2.in","r",stdin);
scanf("%d",&n);
for(i=1;i<=n;++i){
scanf("%s",&snr);
strcat(sir,snr);
}
L=strlen(sir);
for(i=1;i<=L;++i)
v[i]=sir[i-1]-'0';
fclose(stdin);
for(i=0;i<4;++i)
for(j=0;j<=n;++j)
S[i][j]=-1;
S[0][0]=0;S[1][1]=v[1];S[2][1]=v[1]*10+v[2];
if(v[2])S[2][2]=v[1]+v[2];
S[3][1]=v[1]*100+v[2]*10+v[3];
if(v[2])S[3][2]=v[1]+v[2]*10+v[3];
if(v[3] && S[3][2]<v[1]*10+v[2]+v[3]) S[3][2]=v[1]*10+v[2]+v[3];
if(v[2] && v[3])S[3][3]=v[1]+v[2]+v[3];
for(i=4;i<=L;i++){
S[i%4][0]=-1;S[i%4][1]=-1;
for(j=2;j<=i;j++){
if(v[i]==0)S[i%4][j]=-1;
else{
if(S[(i-1+4)%4][j-1]!=-1){
nou=S[(i-1+4)%4][j-1]+v[i];
S[i%4][j]=nou;
}
}
if(v[i-1]>0)
if(S[(i-2+4)%4][j-1]!=-1){
nou=S[(i-2+4)%4][j-1]+v[i-1]*10+v[i];
if(nou>S[i%4][j])
S[i%4][j]=nou;
}
if(v[i-2]>0)
if(S[(i-3+4)%4][j-1]!=-1){
nou=S[(i-3+4)%4][j-1]+v[i-2]*100+v[i-1]*10+v[i];
if(nou>S[i%4][j])
S[i%4][j]=nou;
}
}
}
freopen("suma2.out","w",stdout);
printf("%ld\n",S[L%4][n]);
fclose(stdout);
return 0;
}