首页 > 代码库 > Codeforces Round #267 (Div. 2) C. George and Job （dp）

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

2024-07-26 13:54:02   225人阅读

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

8170436                2014-10-11 06:41:51    njczy2010                    C - George and Job                         GNU C++    Accepted109 ms196172 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 ≤ n; ri - li + 1 = m), 

in such a way that the value of sum 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)水过。

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

 

 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 500514 #define M 100000515 #define mod 100000000716 //#define p 1000000717 #define mod2 10000000018 #define ll long long19 #define LL long long20 #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\n",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             else62                 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\n",i,j,DP(i,j));73     //    }74    // }75     printf("%I64d\n",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 }

 

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


联系
我们