Κοινή χρήση τεχνολογίας

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

1. Περιγραφή προβλήματος

2. Αλγοριθμικές Σκέψεις  

Για την επίλυση αυτού του προβλήματος μπορεί να χρησιμοποιηθεί δυναμικός προγραμματισμός.

Αρχικά, χωρίστε τη συμβολοσειρά αριθμών σε πολλούς αριθμούς και χρησιμοποιήστε έναν πίνακα αριθμών για να αποθηκεύσετε κάθε αριθμό. Για παράδειγμα, η συμβολοσειρά αριθμών 79846 θα χωριστεί στον πίνακα [7, 9, 8, 4, 6].

Στη συνέχεια, ορίστε έναν δισδιάστατο πίνακα dp, όπου το dp[i][j] αντιπροσωπεύει την ελάχιστη τιμή που μπορεί να ληφθεί εισάγοντας σύμβολα j συν στους πρώτους αριθμούς i. Αρχικοποιήστε τον πίνακα dp στο άπειρο, εκτός από το dp[0][0] = 0.

Στη συνέχεια, χρησιμοποιήστε δύο βρόχους για να ενημερώσετε τον πίνακα dp. Ο εξωτερικός βρόχος διασχίζει κάθε αριθμό στη συμβολοσειρά αριθμών και ο εσωτερικός βρόχος διασχίζει τον αριθμό των εισαγόμενων συμβόλων συν. Για κάθε dp[i][j], μπορείτε να εξετάσετε το ενδεχόμενο να συνδυάσετε τον αριθμό nums[i] με τον προηγούμενο αριθμό για να σχηματίσετε έναν νέο αριθμό ή να εισαγάγετε ένα σύμβολο συν μεταξύ του αριθμού nums[i] και του προηγούμενου αριθμού. Πάρτε τη μικρότερη τιμή των δύο καταστάσεων ως τιμή του dp[i][j].

Τέλος, η ελάχιστη τιμή στην τελευταία σειρά του πίνακα dp είναι η ελάχιστη τιμή που αναζητείται.

3. Εφαρμογή κώδικα  

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

Αποτελέσματα του

 συμπέρασμα       

επιθυμία να αυξηθεί ο ενθουσιασμός

Η επιμονή μπορεί να λειάνει τα βουνά

！！！