2015
04-14

# Sleeping

ZZZ is an enthusiastic ACMer and he spends lots of time on training. He always stays up late for training. He needs enough time to sleep, and hates skipping classes. So he always sleeps in the class. With the final exams coming, he has to spare some time to listen to the teacher. Today, he hears that the teacher will have a revision class. The class is N (1 <= N <= 1000) minutes long. If ZZZ listens to the teacher in the i-th minute, he can get Ai points (1<=Ai<=1000). If he starts listening, he will listen to the teacher at least L (1 <= L <= N) minutes consecutively. Its the most important that he must have at least M (1 <= M <= N) minutes for sleeping (the M minutes neednt be consecutive). Suppose ZZZ knows the points he can get in every minute. Now help ZZZ to compute the maximal points he can get.

The input contains several cases. The first line of each case contains three integers N, M, L mentioned in the description. The second line follows N integers separated by spaces. The i-th integer Ai means there are Ai points in the i-th minute.

The input contains several cases. The first line of each case contains three integers N, M, L mentioned in the description. The second line follows N integers separated by spaces. The i-th integer Ai means there are Ai points in the i-th minute.

10 3 3
1 2 3 4 5 6 7 8 9 10

49

code:

#include <cstdio>
#include <cstring>
#define N 1010
#define Max( a, b ) ( a > b ? a : b )
using namespace std;

int dp[ N ];

int cmp[ N ], sum[ N ];

void init ( int n ) {
memset ( cmp, 0, sizeof ( cmp ) );
for ( int i = 1 ; i < n ; ++i ) {
sum[ i ] += sum[ i - 1 ];
}
}

int solve ( int n, int m, int l ) {
init ( n );
for ( int j = 0 ; j <= m ; ++j ) {
int div = j;
memset ( dp, 0, sizeof ( dp ) );
for ( int i = j + 1 ; i <= n ; ++i ) {
dp[ i ] = Max ( dp[ i ], cmp[ i - j ] );
if ( i - l < j ) continue;
if ( dp[ div ] + sum[ i - 1 ] - sum[ div - 1 ] <
dp[ i - l ] + sum[ i - 1 ] - sum[ i - l - 1 ] ) {
div = i - l;
}
dp[ i ] = Max ( dp[ i ], dp[ div ] + sum[ i - 1 ] - sum[ div - 1 ] );
cmp[ i - j ] = Max ( cmp[ i - j ], dp[ i ] );
}
}
return dp[ n ];
}

int main () {
int n, m, l;
while ( scanf ( "%d%d%d", &n, &m, &l ) != EOF ) {
for ( int i = 0 ; i < n ; ++i ) {
scanf ( "%d", &sum[ i ] );
}
printf ( "%d\n", solve ( n, m, l ) );
}
return 0;
}


1. #include <stdio.h>
int main()
{
int n,p,t[100]={1};
for(int i=1;i<100;i++)
t =i;
while(scanf("%d",&n)&&n!=0){
if(n==1)
printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
else {
if(n%4) p=n/4+1;
else p=n/4;
int q=4*p;
printf("Printing order for %d pages:n",n);
for(int i=0;i<p;i++){
printf("Sheet %d, front: ",i+1);
if(q>n) {printf("Blank, %dn",t[2*i+1]);}
else {printf("%d, %dn",q,t[2*i+1]);}
q–;//打印表前
printf("Sheet %d, back : ",i+1);
if(q>n) {printf("%d, Blankn",t[2*i+2]);}
else {printf("%d, %dn",t[2*i+2],q);}
q–;//打印表后
}
}
}
return 0;
}

2. 嗯 分析得很到位，确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样：push时，比较要push的elem和辅助栈的栈顶，elem<=min.top()，则min.push(elem).否则只要push（elem）就好。在pop的时候，比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();}，否则{stack.pop();}.

3. 嗯 分析得很到位，确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样：push时，比较要push的elem和辅助栈的栈顶，elem<=min.top()，则min.push(elem).否则只要push（elem）就好。在pop的时候，比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();}，否则{stack.pop();}.