Technology sharing

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

1. Problem descriptionem

2. Cogitata Algorithmica  

Programmatio dynamica adhiberi potest ad hanc quaestionem solvendam.

Primum, chorda numerum in numerosos divide, et numeros ordinatos utere ad quemlibet numerum congregem. Verbi gratia, numerus chordae 79846 fisus erit in ordinata [7, 9, 8, 4, 6].

Deinde definias duo dimensiva ordinata dp, ubi dp[i][j] valorem minimum, qui obtineri potest, inserendo j plus signa in primum i numeros. Initialize dp ordinata in infinitum, excepto dp[0][0] = 0 .

Tum utere binis ansulis ad dp ordinatam update. Ansa exterior quemque numerum in chorda percurrit, et ansa interior numerum additorum plus signorum percurrit. Utraque enim dp[i][j] considerare potes numerum nums[i] cum priore coniungendo ad novum numerum formandum, vel addito plus signo inter numerum nums[i] et numerum priorem. Minorem valorem duarum condicionum ut valor dp[i][j] adhibe.

Denique minimi pretii in ultimo ordine instrumenti dp ordinati minimi valoris quaesitus est.

3. Code implementation  

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

Proventus of the

 conclusio       

studium augere cupio

Perseverantia potest lenire montes

！！！