Codeforces Round #267 (Div. 2) C. George and Job （dp）

wa哭了，，t哭了，，还是看了题解。。。

8170436	2014-10-11 06:41:51	njczy2010	C - George and Job	GNU C++	Accepted	109 ms	196172 KB
8170430	2014-10-11 06:39:47	njczy2010	C - George and Job	GNU C++	Wrong answer on test 1	61 ms	196200 KB
8170420	2014-10-11 06:37:14	njczy2010	C - George and Job	GNU C++	Runtime error on test 23	140 ms	196200 KB
8170348	2014-10-11 06:16:59	njczy2010	C - George and Job	GNU C++	Time limit exceeded on test 11	1000 ms	196200 KB
8170304	2014-10-11 06:05:15	njczy2010	C - George and Job	GNU C++	Time limit exceeded on test 12	1000 ms	196200 KB
8170271	2014-10-11 05:53:29	njczy2010	C - George and Job	GNU C++	Wrong answer on test 3	77 ms	196200 KB
8170266	2014-10-11 05:52:37	njczy2010	C - George and Job	GNU C++	Wrong answer on test 3	62 ms	196200 KB
8170223	2014-10-11 05:39:00	njczy2010	C - George and Job	GNU C++	Time limit exceeded on test 12	1000 ms	196100 KB
8170135	2014-10-11 05:07:06	njczy2010	C - George and Job	GNU C++	Wrong answer on test 9	93 ms	196100 KB
8170120	2014-10-11 05:01:28	njczy2010	C - George and Job	GNU C++	Wrong answer on test 5	78 ms	196100 KB

The new ITone 6 has been released recently and George got really keen to buy it. Unfortunately, he didn't have enough money, so George was going to work as a programmer. Now he faced the following problem at the work.

Given a sequence of n integers p₁, p₂, ..., p_n. You are to choose k pairs of integers:

[l₁, r₁], [l₂, r₂], ..., [l_k, r_k] (1 ≤ l₁ ≤ r₁ < l₂ ≤ r₂ < ... < l_k ≤ r_k ≤ n; r_i - l_i + 1 = m),

in such a way that the value of sum $\text{[math]}$ is maximal possible. Help George to cope with the task.

Input

The first line contains three integers n, m and k (1 ≤ (m × k) ≤ n ≤ 5000). The second line contains n integers p₁, p₂, ..., p_n (0 ≤ p_i ≤ 10⁹).

Output

Print an integer in a single line — the maximum possible value of sum.

Sample test(s)

Input

5 2 1 1 2 3 4 5

Output

Input

7 1 3 2 10 7 18 5 33 0

Output

转移方程为

dp[i][j]=max(dp[i+1][j],dp[i+m][j-1]+sum[i]);  （转自：http://www.tuicool.com/articles/m6v6z23）


C:显然是dp,设f[i][j]表示第i段的结尾为j时的最优值，显然f[i][j]=max{f[i-1][k]+sum[j]-sum[j-m]}(0<=k<=j-m) （转自：http://www.bkjia.com/ASPjc/881176.html）

不过这样是O(k*n^2),可能超时。

我们发现每一阶段的转移能用到的最优状态都是上一阶段的前缀最优值，于是dp时直接记录下来用来下面的转移，这样就不用枚举了，变为O(k*n)水过。

貌似卡内存，用了滚动数组。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cstdio>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<queue>
 8 #include<map>
 9 #include<set>
10 #include<string>
11 //#include<pair>
12 
13 #define N 5005
14 #define M 1000005
15 #define mod 1000000007
16 //#define p 10000007
17 #define mod2 100000000
18 #define ll long long
19 #define LL long long
20 #define maxi(a,b) (a)>(b)? (a) : (b)
21 #define mini(a,b) (a)<(b)? (a) : (b)
22 
23 using namespace std;
24 
25 int n,m,k;
26 ll dp[N][N];
27 ll p[N];
28 ll ans;
29 ll sum[N];
30 
31 void ini()
32 {
33     memset(dp,0,sizeof(dp));
34     memset(sum,0,sizeof(sum));
35     int i;
36     ll te=0;
37     for(i=1;i<=n;i++){
38         scanf("%I64d",&p[i]);
39     }
40 
41     for(i=n-m+1;i<=n;i++){
42         te+=p[i];
43     }
44     sum[n-m+1]=te;
45     dp[n-m+1][1]=te;
46    // ma=te;
47     for(i=n-m;i>=1;i--){
48         sum[i]=sum[i+1]+p[i]-p[i+m];
49     }
50     //for(i=1;i<=n;i++) printf(" i=%d sum=%I64d
",i,sum[i]);
51 }
52 
53 void solve()
54 {
55     int i,j;
56     dp[n][1]=sum[n];
57     for(i=n-1;i>=1;i--){
58         for(j=k;j>=1;j--){
59             if(i+m<=n+1)
60                 dp[i][j]=max(dp[i+1][j],dp[i+m][j-1]+sum[i]);
61             else
62                 dp[i][j]=dp[i+1][j];
63         }
64     }
65 
66 }
67 
68 void out()
69 {
70     //for(int i=1;i<=n;i++){
71     //    for(int j=0;j<=k;j++){
72     //        printf(" i=%d j=%d dp=%I64d
",i,j,DP(i,j));
73     //    }
74    // }
75     printf("%I64d
",dp[1][k]);
76 }
77 
78 int main()
79 {
80    // freopen("data.in","r",stdin);
81     //freopen("data.out","w",stdout);
82    // scanf("%d",&T);
83    // for(int ccnt=1;ccnt<=T;ccnt++)
84    // while(T--)
85     while(scanf("%d%d%d",&n,&m,&k)!=EOF)
86     {
87         //if(n==0 && k==0 ) break;
88         //printf("Case %d: ",ccnt);
89         ini();
90         solve();
91         out();
92     }
93 
94     return 0;
95 }