A. L'importance d'une lecture attentive des énoncés
Cette quesiton implémentait une optimisation de la programmation dynamique à l'aide d'une file monotone, un schéma récurrent similaire à celui de la question C de la veille.

B. Obtenir des points même avec une solution brute-force
Le problème est basé sur P1758 [NOI2009] de Luogu. Il s'agit d'un problème de programmation dynamique assez complexe. On dispose de deux séquences composées de deux types de caractères. À chaque étape, on retire le dernier caractère d'une des séquences et on l'ajoute à une nouvelle séquence. On cherche à calculer la somme des carrés du nombre de chemins pour chaque forme finale distincte.

La conversion de la somme des carrés en comptage de paires de chemins identiques est une idée clé. On utilise une fonction à quatre dimensions, mais on peut réduire une dimension car i + j = x + y. L'utilisation d'un tableau roulant permet d'optimiser la mémoire.

#include <iostream>
#include <cstring>
using namespace std;

const int MAXLEN = 510;
const int MODULO = 1024523;
int n, m;
char str1[MAXLEN], str2[MAXLEN];
int dp[2][MAXLEN][MAXLEN];

int main() {
    cin >> n >> m;
    cin >> str1 + 1 >> str2 + 1;
    dp[0][0][0] = 1;
    int parity = 0;
    for (int pos = 0; pos <= n; pos++, parity ^= 1) {
        for (int cnt2 = 0; cnt2 <= m; cnt2++) {
            for (int x = 0; x <= n; x++) {
                int y = pos + cnt2 - x;
                int val = dp[parity][cnt2][x];
                if (val == 0 || y < 0 || y > m) continue;
                if (str1[pos + 1] == str1[x + 1]) {
                    dp[parity ^ 1][cnt2][x + 1] = (dp[parity ^ 1][cnt2][x + 1] + val) % MODULO;
                }
                if (str1[pos + 1] == str2[y + 1]) {
                    dp[parity ^ 1][cnt2][x] = (val + dp[parity ^ 1][cnt2][x]) % MODULO;
                }
                if (str2[cnt2 + 1] == str1[x + 1]) {
                    dp[parity][cnt2 + 1][x + 1] = (val + dp[parity][cnt2 + 1][x + 1]) % MODULO;
                }
                if (str2[cnt2 + 1] == str2[y + 1]) {
                    dp[parity][cnt2 + 1][x] = (val + dp[parity][cnt2 + 1][x]) % MODULO;
                }
                dp[parity][cnt2][x] = 0;
            }
        }
    }
    cout << dp[parity][m][n] << endl;
    return 0;
}

C. Supprimer les instructions de débogage avant la soumission
Problème basé sur P2885 [USACO07NOV] de Luogu. On doit ajuster les hauteurs d'arbres avec un coût quadratique, puis connecter les arbres avec un coût proportinonel à la différence de hauteur. L'objectif est de minimiser la somme des coûts.

Une approche par programmation dynamique de base est en O(n*h^2). Pour l'optimiser, on sépare les cas en fonction de la relation entre les hauteurs, ce qui permet de réduire la complexité à O(n*h).

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

const int MAXN = 100002;
const int MAXH = 102;
const int INF = 0x3f3f3f3f;
int nbTrees, costFactor;
int heights[MAXN];
int dp[MAXN][MAXH];

int main() {
    cin >> nbTrees >> costFactor;
    int maxHeight = 0;
    for (int i = 1; i <= nbTrees; i++) {
        cin >> heights[i];
        maxHeight = max(maxHeight, heights[i]);
    }
    memset(dp, 0x3f, sizeof(dp));
    for (int h = heights[1]; h <= maxHeight; h++) {
        dp[1][h] = (heights[1] - h) * (heights[1] - h);
    }
    for (int i = 2; i <= nbTrees; i++) {
        int minValue = INF;
        for (int prevH = 1; prevH <= heights[i]; prevH++) {
            minValue = min(minValue, dp[i - 1][prevH] - costFactor * prevH);
        }
        for (int currH = heights[i]; currH <= maxHeight; currH++) {
            minValue = min(minValue, dp[i - 1][currH] - costFactor * currH);
            dp[i][currH] = min(dp[i][currH], minValue + costFactor * currH + (currH - heights[i]) * (currH - heights[i]));
        }
        minValue = INF;
        for (int currH = maxHeight; currH >= heights[i]; currH--) {
            minValue = min(minValue, dp[i - 1][currH] + costFactor * currH);
            dp[i][currH] = min(dp[i][currH], minValue - costFactor * currH + (currH - heights[i]) * (currH - heights[i]));
        }
    }
    int result = INF;
    for (int h = heights[nbTrees]; h <= maxHeight; h++) {
        result = min(result, dp[nbTrees][h]);
    }
    cout << result << endl;
    return 0;
}

D. Le glouton ne fonctionne que sur les exemples
Ce problème impliquait de déterminer le nombre de valeurs distinctes obtenues en sommant les carrés des éléments choisis sur deux lignes de nombres. Une solution efficace utilise la programmation dynamique avec compression d'états, où on marque si une somme est atteignable à chaque étape.

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 104;
const int MAXSUM = MAXN * MAXN * MAXN;
int n;
int values[MAXN][2];
bool reachable[MAXN][MAXSUM];
long long countDistinct = 0;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> values[i][0] >> values[i][1];
    }
    reachable[1][values[1][0] * values[1][0]] = true;
    reachable[1][values[1][1] * values[1][1]] = true;
    for (int step = 2; step <= n; step++) {
        for (int sum = 1; sum <= step * MAXN * MAXN; sum++) {
            if (sum - values[step][0] * values[step][0] > 0) {
                reachable[step][sum] |= reachable[step - 1][sum - values[step][0] * values[step][0]];
            }
            if (sum - values[step][1] * values[step][1] > 0) {
                reachable[step][sum] |= reachable[step - 1][sum - values[step][1] * values[step][1]];
            }
        }
    }
    for (int sum = 1; sum <= n * MAXN * MAXN; sum++) {
        if (reachable[n][sum]) {
            countDistinct++;
        }
    }
    cout << countDistinct << endl;
    return 0;
}