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
C. George and Job
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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 p1, p2, ..., pn. You are to choose k pairs of integers:

[l1, r1], [l2, r2], ..., [lk, rk] (1 ≤ l1 ≤ r1 < l2 ≤ r2 < ... < lk ≤ rk ≤ nri - li + 1 = m), 

in such a way that the value of sum Codeforces Round #267 (Div. 2)  C. George and Job (dp) 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 p1, p2, ..., pn (0 ≤ pi ≤ 109).

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
9
Input
7 1 3 2 10 7 18 5 33 0
Output
61

转移方程为

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)水过。

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

 #include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<string>
//#include<pair> #define N 5005
#define M 1000005
#define mod 1000000007
//#define p 10000007
#define mod2 100000000
#define ll long long
#define LL long long
#define maxi(a,b) (a)>(b)? (a) : (b)
#define mini(a,b) (a)<(b)? (a) : (b) using namespace std; int n,m,k;
ll dp[N][N];
ll p[N];
ll ans;
ll sum[N]; void ini()
{
memset(dp,,sizeof(dp));
memset(sum,,sizeof(sum));
int i;
ll te=;
for(i=;i<=n;i++){
scanf("%I64d",&p[i]);
} for(i=n-m+;i<=n;i++){
te+=p[i];
}
sum[n-m+]=te;
dp[n-m+][]=te;
// ma=te;
for(i=n-m;i>=;i--){
sum[i]=sum[i+]+p[i]-p[i+m];
}
//for(i=1;i<=n;i++) printf(" i=%d sum=%I64d\n",i,sum[i]);
} void solve()
{
int i,j;
dp[n][]=sum[n];
for(i=n-;i>=;i--){
for(j=k;j>=;j--){
if(i+m<=n+)
dp[i][j]=max(dp[i+][j],dp[i+m][j-]+sum[i]);
else
dp[i][j]=dp[i+][j];
}
} } void out()
{
//for(int i=1;i<=n;i++){
// for(int j=0;j<=k;j++){
// printf(" i=%d j=%d dp=%I64d\n",i,j,DP(i,j));
// }
// }
printf("%I64d\n",dp[][k]);
} int main()
{
// freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
// scanf("%d",&T);
// for(int ccnt=1;ccnt<=T;ccnt++)
// while(T--)
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
//if(n==0 && k==0 ) break;
//printf("Case %d: ",ccnt);
ini();
solve();
out();
} return ;
}
上一篇:Codeforces 467C George and Job(DP)


下一篇:使用SSL协议保证web服务通信安全(二、实战篇)