informasi kontak saya
Surat[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
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.
- #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;
- }
Kesimpulan
keinginan untuk meningkatkan semangat
Ketekunan mampu menghaluskan gunung
!!!