Description

給定N個整數組成的序列，現在要求將序列分割為M段，每段子序列中的數在原序列中連續排列。如何分割才能使這M段子序列的和的最大值達到最小？

編程任務：給定N個整數組成的序列，編程計算該序列的最優M段分割，使M段子序列的和的最大值達到最小。

Input

輸入的第一行有2個正整數N和M。正整數N是序列的長度；正整數M是分割的斷數。接下來的一行中有N個整數。

Output

輸出一行即：M段子序列的和的最大值的最小值。

Sample Input

1 1
10

Sample Output

10

Hint

樣例二：
輸入：
9 3
9 8 7 6 5 4 3 2 1
輸出：

17?

code

#include <bits/stdc++.h> using namespace std; #define N 200 int dp[N][N] ;//dp(i,j)表示前i個數據的j劃分 int main(){int n,m;int a[N] ;while (cin>>n>>m){for(int i = 0; i<n ;++i){cin>>a[i];if (i==0)dp[i][1] = a[i];elsedp[i][1] =dp[i-1][1]+a[i];}dp[0][0] = 0;//dp[1][1] = a[0] ;for(int i = 1; i < n ;++i){for(int j = 2; j-1 <= i&&j<=m ;++j){dp[i][j] = 0x7fffffff;for (int k = i-1 ; k >= 0 ; --k){dp[i][j] = min(dp[i][j] , max(dp[i][1]-dp[k][1] ,dp[k][j-1]));}}}cout<<dp[n-1][m];}return 0; }

總結

以上是生活随笔為你收集整理的最小m段和问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。