洛谷 P1281 书的复制

题目传送门

解题思路:

f[i][j]表示表示i本书分给j个人抄的最佳答案.最后贪心找答案.
AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 int m,k,a[501],f[501][501],u,ansi[501],ansj[501],ans = 99999999,sum[501];
 8 
 9 inline int min(int s,int d) {
10     if(s >= d) return d;
11     return s;
12 }
13 
14 inline int max(int s,int d) {
15     if(s >= d) return s;
16     return d;
17 }
18 
19 inline void find_answer() {
20     int n = 0,end = m,id = k;
21     for(int i = m;i >= 1; i--) {
22         n += a[i];
23         if(n > ans) {
24             ansi[id] = i + 1;
25             ansj[id] = end;
26             end = i,n = 0,i++,id--;
27         }
28     }
29     ansi[id] = 1;
30     ansj[id] = end;
31 }
32 
33 int main() {
34     memset(f,0x3f3f3f,sizeof(f));
35     scanf("%d%d",&m,&k);
36     for(int i = 1;i <= m; i++) {
37         scanf("%d",&a[i]);
38         sum[i] = sum[i-1] + a[i];
39         f[i][1] = sum[i];
40     }
41     for(int j = 2;j <= k; j++)
42         for(int i = j;i <= m; i++)
43             for(int k = j;k <= i; k++) {
44                 u = max(f[k-1][j-1],sum[i] - sum[k-1]);
45                 f[i][j] = min(f[i][j],u);
46             }
47     ans = f[m][k];
48     find_answer();
49     for(int i = 1;i <= k; i++)
50         printf("%d %d
",ansi[i],ansj[i]);
51     return 0;
52 }