Technologieaustausch

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

1. Problembeschreibung

2. Algorithmische Gedanken  

Zur Lösung dieses Problems kann dynamische Programmierung eingesetzt werden.

Teilen Sie zunächst die Zahlenfolge in mehrere Zahlen auf und verwenden Sie ein Array „nums“, um jede Zahl zu speichern. Beispielsweise wird die Zahlenfolge 79846 in das Array [7, 9, 8, 4, 6] aufgeteilt.

Definieren Sie dann ein zweidimensionales Array dp, wobei dp[i][j] den Mindestwert darstellt, der durch Einfügen von j Pluszeichen in die ersten i Zahlen erhalten werden kann. Initialisieren Sie das dp-Array auf unendlich, außer dp[0][0] = 0.

Verwenden Sie dann zwei Schleifen, um das dp-Array zu aktualisieren. Die äußere Schleife durchläuft jede Zahl in der Zahlenfolge und die innere Schleife durchläuft die Anzahl der eingefügten Pluszeichen. Für jedes dp[i][j] können Sie erwägen, die Zahl nums[i] mit der vorherigen Zahl zu kombinieren, um eine neue Zahl zu bilden, oder ein Pluszeichen zwischen der Zahl nums[i] und der vorherigen Zahl einzufügen. Nehmen Sie den kleineren Wert der beiden Fälle als Wert von dp[i][j].

Schließlich ist der Minimalwert in der letzten Zeile des dp-Arrays der gesuchte Minimalwert.

3. Code-Implementierung  

#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;
}

Ergebnisse der

 Abschluss       

Wunsch, die Begeisterung zu steigern

Ausdauer kann die Berge glätten

！！！