Untitled
unknown
plain_text
a year ago
1.1 kB
5
Indexable
#include <iostream> #include <algorithm> using namespace std; int main() { int n, m; cin >> n >> m; int numbers[n]; for (int i = 0; i < n; ++i) { cin >> numbers[i]; } int dp[n + 1][m + 1]; // Khởi tạo giá trị cho hàng đầu tiên của mảng. for (int i = 0; i <= n; ++i) { dp[i][1] = 0; for (int j = 0; j < i; ++j) { dp[i][1] += numbers[j]; } } // Khởi tạo giá trị cho cột đầu tiên của mảng. for (int j = 0; j <= m; ++j) { dp[0][j] = 0; } // Tính toán giá trị cho các phần tử còn lại của mảng. for (int j = 2; j <= m; ++j) { for (int i = 1; i <= n; ++i) { dp[i][j] = INT_MAX; int sum = 0; for (int k = i; k > 0; --k) { sum += numbers[k - 1]; dp[i][j] = min(dp[i][j], max(dp[k - 1][j - 1], sum)); } } } cout << "Maximum sum among minimum sums in each group: " << dp[n][m] << endl; return 0; }
Editor is loading...
Leave a Comment