Partage de technologie

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. Description du problème

2. Pensées algorithmiques  

La programmation dynamique peut être utilisée pour résoudre ce problème.

Tout d’abord, divisez la chaîne numérique en plusieurs nombres et utilisez un tableau nums pour stocker chaque nombre. Par exemple, la chaîne numérique 79846 sera divisée en tableau [7, 9, 8, 4, 6].

Définissez ensuite un tableau bidimensionnel dp, où dp[i][j] représente la valeur minimale pouvant être obtenue en insérant j signes plus dans les i premiers nombres. Initialisez le tableau dp à l'infini, sauf pour dp[0][0] = 0.

Utilisez ensuite deux boucles pour mettre à jour le tableau dp. La boucle externe parcourt chaque nombre de la chaîne numérique et la boucle interne parcourt le nombre de signes plus insérés. Pour chaque dp[i][j], vous pouvez envisager de combiner le nombre nums[i] avec le nombre précédent pour former un nouveau nombre, ou d'insérer un signe plus entre le nombre nums[i] et le nombre précédent. Prenez la plus petite valeur des deux situations comme valeur de dp[i][j].

Enfin, la valeur minimale de la dernière ligne du tableau dp est la valeur minimale recherchée.

3. Mise en œuvre du code  

#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
 
// Helper function to extract integer value from substring
int getNumber(char* str, int start, int end) {
    char buffer[12]; // Buffer large enough for max 10 digits + '0'
    int length = end - start + 1;
    strncpy(buffer, str + start, length);
    buffer[length] = '0';
    return atoi(buffer);
}
 
int main() {
    char str[201];
    int M;
    scanf("%s %d", str, &M);
    
    int n = strlen(str);
    int dp[n+1][M+1];
    
    // Initialize dp array with large numbers
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= M; j++) {
            dp[i][j] = INT_MAX;
        }
    }
    
    // Base case: no splits
    dp[0][0] = 0;
    
    // Dynamic programming to calculate minimum sum
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= M; j++) { // j can be 0 as well
            if (j == 0) {
                dp[i][j] = getNumber(str, 0, i-1);
            } else {
                for (int k = 1; k < i; k++) { // k starts from 1
                    if (dp[k][j-1] != INT_MAX) {
                        int num = getNumber(str, k, i-1);
                        if (dp[k][j-1] + num < dp[i][j]) {
                            dp[i][j] = dp[k][j-1] + num;
                        }
                    }
                }
            }
        }
    }
    
    // Find the minimum value in dp[n][*] with M splits
    int result = INT_MAX;
    for (int i = 0; i <= M; i++) {
        if (dp[n][i] < result) {
            result = dp[n][i];
        }
    }
    
    printf("%dn", result);
    return 0;
}

Résultats du

 Conclusion       

désir d'augmenter l'enthousiasme

La persévérance peut aplanir les montagnes

！！！