Comment dois-je résoudre le contournement d’autoroute d’INOI 2014?

Il s’agit d’un problème DP à 4 dimensions. Il est facile de sauvegarder la variable D ce qui restreint le nombre maximum de segments consécutifs que l’on peut parcourir dans une direction. Donc, finalement, nous avons besoin de 4 variables:
i: pour les lignes
j: pour les colonnes
d: pour un mouvement restreint dans une direction consécutive.
et un drapeau pour indiquer la direction que vous souhaitez déplacer (c’est-à-dire vers la droite ou vers le bas).

Maintenant, voyez, pour tout débloqué (i, j) de ( R , C ) à (0,0),
count (i, j, D , 0) = count (i + 1, j, 1,1)
count (i, j, D , 1) = count (i, j + 1,1,1)
Alors pour tout d en D
          count (i, j, d, 0) = count (i, j + 1, d + 1,0) + count (i + 1, j, 1,1)
count (i, j, d, 1) = count (i + 1, j, d + 1,1) + count (i, j + 1,1,0)
Cette construction récursive prendra un temps exponentiel à résoudre. Alors souviens-toi. Ensuite, il faudra O ( RCD ). Si R = C = D = n, alors il faudrait O (n ^ 3).

Il peut également être implémenté dans deux DP 2d.

Voici la solution –

#include
#include

using namespace std;

int main(){
int c, r, d;
cin >> c >> r >> d;

vecteur > a (c, vecteur (r, 0));
vecteur > ft (c, vecteur (r, 0));
vecteur > fl (c, vecteur (r, 0));

pour (int i = 0; i pour (int j = 0; j cin >> a [i] [j];
}

}

ft [0] [0] = 1;
fl [0] [0] = 1;

pour (int i = 0; i pour (int j = 0; j if ((i == 0 && j == 0) ||! a [i] [j]) {
continuer;
}
int voies = 0;
int minim = id;
si (minim <0) {
minim = 0;
}
pour (int k = i-1; k> = minim; k -) {
si (! (a [k] [j])) {
Pause;
}
voies + = ft [k] [j];
}
fl [i] [j] = voies% 20011;

voies = 0;
minim = jd;
si (minim <0) {
minim = 0;
}
pour (int k = j-1; k> = minim; k -) {
si (! (a [i] [k])) {
Pause;
}
voies + = fl [i] [k];
}
ft [i] [j] = voies% 20011;
}
}
int ans = (fl [c-1] [r-1] + ft [c-1] [r-1])% 20011;
cout << ans << endl;
retourner 0;
}

Modifier: le crédit de la solution va à: User-11721075346072916303. Il m’a expliqué l’approche de ce problème.

les gars j’ai du mal à prendre des commentaires. quelqu’un peut-il aider. http://pastebin.com/cqqH8JRs