此题主要采用DP思路，难点是求解"/"，需要考虑划分数量不够的情况，先采用DP求解最优解，然后采用贪心求解slash。防止中间结果出错，使用了unsigned int。
#includeusing namespace std;#define MAXNUM 501unsigned int pages[MAXNUM][MAXNUM];int main() { int case_n, m, k; int i, j, p, q; unsigned min, tmp, sum; cin >>case_n; for (p=1; p<=case_n; ++p) { cin >>m>>k; for (i=1; i<=m; ++i) cin >>pages[0][i]; // handle the One worker case pages[1][1] = pages[0][1]; for (i=2; i<=m ;++i) pages[1][i] = pages[0][i] + pages[1][i-1]; for (i=2; i<=k; i++) { for (j=1; j<=m; j++) { if (i>j) { pages[i][j] = pages[i-1][j]; } else { min = pages[i-1][j]; sum = 0; for (q=j-1; q>=i-1; q--) { sum += pages[0][q+1]; tmp = (sum > pages[i-1][q]) ? sum : pages[i-1][q]; if (tmp <= min) min = tmp; else break; } pages[i][j] = min; } } } bool slash[MAXNUM] = { false}; int slash_num = 0; sum = 0; for (i=m; i>=1; i--) { if (sum + pages[0][i] > pages[k][m]) { slash[i] = true; slash_num++; sum = pages[0][i]; } else { sum += pages[0][i]; } } if (slash_num < k-1) { for (i=1; i<=m && slash_num != k-1; i++) { if ( !slash[i] ) { slash[i] = true; slash_num++; } } } for (i=1; i