Sleeping
2856 단어 동적 기획
시간 제한:
1000ms | 메모리 제한:
65535 KB
난이도:
3
묘사
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. It`s the most important that he must have at least M (1 <= M <= N) minutes for sleeping (the M minutes needn`t 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.
출력
For each test case, output an integer, indicating the maximal points ZZZ can get.
샘플 입력
10 3 31 2 3 4 5 6 7 8 9 10
샘플 출력
49
제목:
n ,ZZZ , L , m ( m ),
, 。。。
사고방식: 비교적 이해하기 어려운 dp, 특히 tdp[i]가 대표하는 의미.
#include <stdio.h>
#include <string.h>
int dp[1001][1001], tdp[1001], sum[1001]; //dp[i][j]: i j , tdp[j]: i j , ( i-l i )
int mymax(int a, int b)
{
return a > b ? a : b;
}
int main()
{
int n, m, l, i, j;
while(scanf("%d%d%d", &n, &m, &l) != EOF)
{
memset(dp, 0, sizeof(dp));
memset(tdp, 0, sizeof(tdp));
sum[0] = 0;
for(i = 1; i <= n; i++)
{
scanf("%d", &sum[i]);
sum[i] += sum[i-1]; // i
}
for(i = 1; i <= n; i++)
{
for(j = 0; j <= m && j <= i; j++)
{
dp[i][j] = j >= 1 ? dp[i-1][j-1] : 0; // i
if(i-j >= l) // l
{
tdp[j] = mymax(tdp[j]+sum[i]-sum[i-1], dp[i-l][j]+sum[i]-sum[i-l]); // tdp[j] ( dp[i-l][j]+... l l )
}
dp[i][j] = mymax(tdp[j], dp[i][j]); //
}
}
printf("%d
", dp[n][m]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.