C. George and Job

62 阅读 0 评论 41 点赞

我是靠谱客的博主糟糕花生，最近开发中收集的这篇文章主要介绍C. George and Job，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：

　　　　http://codeforces.com/contest/467/problem/C

· 二维DP

· 题目中其实也有一个特点数字： 5000，预示着可能使用二维dp。int f[5050][5050]可以开下，但是int f[10010][10010] 有的OJ就不行了

· 注意结果会超int 。

dp[i][j]表示在取到第i个元素的时候取j个m长度的区间之和的最大值。

dp[i][j]可由dp[i-1][j]不添加区间得到的,或者由dp[i-m][j-1]添加一个区间得到。

遂有状态转移方程：dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+s[i]-s[i-m])，（其中s是前缀和。）

AC Code：

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #include <string.h>
 5 #include <queue>
 6 using namespace std;
 7 #define LL long long
 8 #define N 5050
 9 int deal(int i){
10 
11 
12 }
13 LL f[N],sum[N],dp[N][N];
14 int main(){
15     freopen("in.txt","r",stdin);
16     //freopen("out.txt","w",stdout);
17     //状态转移方程： dp[i][j] = dp[i-1][j] / dp[i-m][j-1] + sum[i]-sum[i-m];
18     int n,m,k;
19     while(cin>>n>>m>>k){
20         for(int i=1;i<=n;i++) scanf("%d",&f[i]);
21         LL num=0;
22         for(int i=1;i<=n;i++){
23             num += f[i]; sum[i] = num; //前缀和
24         }
25         //printf(" sum : %d -- m :%dn",num,m);
26         memset(dp,0,sizeof(dp));
27         for(int i=1;i<=n;i++){
28             for(int j=1;j<=k;j++){
29                 //前i个数字，取j段 m 长的数字；
30                 if(i-m>=0)
31                     dp[i][j] = max(dp[i-1][j],dp[i-m][j-1]+sum[i]-sum[i-m]);
32             }
33         }
34         printf("%lldn",dp[n][k]);
35     }
36 
37 
38     return 0;
39 }