2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
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.
- #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;
- }
Johtopäätös
halu lisätä innostusta
Sinnikkyys voi tasoittaa vuoria
!!!