2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Zur Lösung dieses Problems kann dynamische Programmierung eingesetzt werden.
Teilen Sie zunächst die Zahlenfolge in mehrere Zahlen auf und verwenden Sie ein Array „nums“, um jede Zahl zu speichern. Beispielsweise wird die Zahlenfolge 79846 in das Array [7, 9, 8, 4, 6] aufgeteilt.
Definieren Sie dann ein zweidimensionales Array dp, wobei dp[i][j] den Mindestwert darstellt, der durch Einfügen von j Pluszeichen in die ersten i Zahlen erhalten werden kann. Initialisieren Sie das dp-Array auf unendlich, außer dp[0][0] = 0.
Verwenden Sie dann zwei Schleifen, um das dp-Array zu aktualisieren. Die äußere Schleife durchläuft jede Zahl in der Zahlenfolge und die innere Schleife durchläuft die Anzahl der eingefügten Pluszeichen. Für jedes dp[i][j] können Sie erwägen, die Zahl nums[i] mit der vorherigen Zahl zu kombinieren, um eine neue Zahl zu bilden, oder ein Pluszeichen zwischen der Zahl nums[i] und der vorherigen Zahl einzufügen. Nehmen Sie den kleineren Wert der beiden Fälle als Wert von dp[i][j].
Schließlich ist der Minimalwert in der letzten Zeile des dp-Arrays der gesuchte Minimalwert.
- #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;
- }
Abschluss
Wunsch, die Begeisterung zu steigern
Ausdauer kann die Berge glätten
!!!