-Có 10 test. Môi test 0.6 diêm -Ðáp án: Sir dung phucng pháp quy hoach dêng Goi: • a[i], b[i]; c[i] lân IUQt là giá tri các ô ð cot i cùa dãi thú 1, thú2 và thú 3; • Ð4t : a[n+1]=0; c[n+1]=0; // Nhåy vào vi trí kêt thúc thì không

duo thêm diêm • DPg[i] là tông diêm nhân duqc khi nhåy dên cot i và dat chân vào ô ð dåi giüa. • DP2b[i] là tðng diêm nhân duqc khi nhåy dên cot i và dät chân vào ô không ð dåi giüa (túc là ð mot trong hai dåi thú nhât hoac thú ba) Khi dó:

for (int i=l;
DPg[i]=-oo; //oo=Vô cuc hmnhut.blogspot.com

for (int j=l ;j<=p;j++) if (i-j>=0) DPg[i]=max(DPg[i], DP2b[i-j]+b[i] );// nhåy vào ô dåi giüa cot i DP2b[i]=max(DP2b[i], DPg[i-j]+max(a[i] ,c[i]));// nhåy vào ô dåi bên ngoài Két quå là: