Technologieaustausch

Touge-Ressourcenbibliothek (24) Pluszeichen einfügen

2024-07-12

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

1. Problembeschreibung

2. Algorithmische Gedanken  

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.

3. Code-Implementierung  

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <limits.h>
  4. #include <stdlib.h>
  5. // Helper function to extract integer value from substring
  6. int getNumber(char* str, int start, int end) {
  7. char buffer[12]; // Buffer large enough for max 10 digits + '0'
  8. int length = end - start + 1;
  9. strncpy(buffer, str + start, length);
  10. buffer[length] = '0';
  11. return atoi(buffer);
  12. }
  13. int main() {
  14. char str[201];
  15. int M;
  16. scanf("%s %d", str, &M);
  17. int n = strlen(str);
  18. int dp[n+1][M+1];
  19. // Initialize dp array with large numbers
  20. for (int i = 0; i <= n; i++) {
  21. for (int j = 0; j <= M; j++) {
  22. dp[i][j] = INT_MAX;
  23. }
  24. }
  25. // Base case: no splits
  26. dp[0][0] = 0;
  27. // Dynamic programming to calculate minimum sum
  28. for (int i = 1; i <= n; i++) {
  29. for (int j = 0; j <= M; j++) { // j can be 0 as well
  30. if (j == 0) {
  31. dp[i][j] = getNumber(str, 0, i-1);
  32. } else {
  33. for (int k = 1; k < i; k++) { // k starts from 1
  34. if (dp[k][j-1] != INT_MAX) {
  35. int num = getNumber(str, k, i-1);
  36. if (dp[k][j-1] + num < dp[i][j]) {
  37. dp[i][j] = dp[k][j-1] + num;
  38. }
  39. }
  40. }
  41. }
  42. }
  43. }
  44. // Find the minimum value in dp[n][*] with M splits
  45. int result = INT_MAX;
  46. for (int i = 0; i <= M; i++) {
  47. if (dp[n][i] < result) {
  48. result = dp[n][i];
  49. }
  50. }
  51. printf("%dn", result);
  52. return 0;
  53. }

Ergebnisse der

 Abschluss       

Wunsch, die Begeisterung zu steigern

Ausdauer kann die Berge glätten

!!!