Berbagi teknologi

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

1. Deskripsi masalah

2. Pemikiran Algoritma  

Pemrograman dinamis dapat digunakan untuk mengatasi masalah ini.

Pertama, pisahkan string angka menjadi beberapa angka, dan gunakan array angka untuk menyimpan setiap angka. Misalnya, string angka 79846 akan dipecah menjadi array [7, 9, 8, 4, 6].

Kemudian tentukan array dua dimensi dp, dimana dp[i][j] mewakili nilai minimum yang dapat diperoleh dengan menyisipkan tanda j plus ke dalam i bilangan pertama. Inisialisasi array dp hingga tak terhingga, kecuali dp[0][0] = 0.

Kemudian gunakan dua loop untuk memperbarui array dp. Perulangan bagian luar melintasi setiap angka dalam rangkaian angka, dan putaran dalam melintasi jumlah tanda tambah yang disisipkan. Untuk setiap dp[i][j], Anda dapat mempertimbangkan untuk menggabungkan angka nums[i] dengan angka sebelumnya untuk membentuk angka baru, atau menyisipkan tanda plus di antara angka nums[i] dan angka sebelumnya. Ambil nilai yang lebih kecil dari kedua kasus tersebut sebagai nilai dp[i][j].

Terakhir, nilai minimum pada baris terakhir array dp adalah nilai minimum yang dicari.

3. Implementasi kode  

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

Hasil dari

 Kesimpulan       

keinginan untuk meningkatkan semangat

Ketekunan mampu menghaluskan gunung

！！！