技術共有

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

1. 問題の説明

2. アルゴリズム的思考  

この問題を解決するには、動的プログラミングを使用できます。

まず、数値文字列を複数の数値に分割し、配列 nums を使用して各数値を格納します。たとえば、数値文字列 79846 は配列 [7, 9, 8, 4, 6] に分割されます。

次に、2 次元配列 dp を定義します。ここで、dp[i][j] は、最初の i 個の数値に j 個のプラス記号を挿入することによって取得できる最小値を表します。 dp[0][0] = 0 を除き、dp 配列を無限大に初期化します。

次に、2 つのループを使用して dp 配列を更新します。外側のループは数値文字列内の各数値を調べ、内側のループは挿入されたプラス記号の数を調べます。各 dp[i][j] について、数値 nums[i] を前の数値と組み合わせて新しい数値を形成するか、数値 nums[i] と前の数値の間にプラス記号を挿入することを検討できます。 2 つの状況のうち小さい方の値を 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;
}

の結果

 結論       

熱意を高めたいという欲求

忍耐力があれば山は平らになる

！！！