Teknologian jakaminen

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

1. Ongelman kuvaus

2. Algoritmiset ajatukset  

Tämän ongelman ratkaisemiseksi voidaan käyttää dynaamista ohjelmointia.

Jaa ensin numeromerkkijono useiksi numeroiksi ja tallenna jokainen numero taulukon numeroiden avulla. Esimerkiksi numeromerkkijono 79846 jaetaan taulukkoon [7, 9, 8, 4, 6].

Määrittele sitten kaksiulotteinen taulukko dp, jossa dp[i][j] edustaa minimiarvoa, joka voidaan saada lisäämällä j plusmerkki ensimmäiseen i numeroon. Alusta dp-taulukko äärettömään, paitsi dp[0][0] = 0.

Käytä sitten kahta silmukkaa dp-taulukon päivittämiseen. Ulompi silmukka kulkee numerojonon jokaisen numeron läpi ja sisempi silmukka lisättyjen plusmerkkien määrän. Voit harkita kunkin dp[i][j]-luvun yhdistämistä numeroiden[i] kanssa edelliseen numeroon uuden luvun muodostamiseksi tai plusmerkin lisäämistä numeroiden [i] ja edellisen luvun väliin. Ota näiden kahden tilanteen pienempi arvo dp[i][j]:n arvoksi.

Lopuksi vähimmäisarvo dp-taulukon viimeisellä rivillä on pienin haettu arvo.

3. Koodin käyttöönotto  

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

Tulokset

 Johtopäätös       

halu lisätä innostusta

Sinnikkyys voi tasoittaa vuoria

！！！