POJ 2479 Maximum sum (2 단 연속 과 최대)
4695 단어 poj
n 개의 수 를 정 하고 연속 적 인 2 단 을 선택 하여 2 단의 합 을 최대 로 합 친다.
생각:
1. 연속 최대 부분 과 이미 매우 전형 적 인 문제 이 므 로 선형 알고리즘 으로 구 할 수 있다.
2. 2 단 연속 최대 화 에 대해 분 치 전략 을 채택 할 수 있 습 니까?
분계 점 i 에 대해 앞의 i 개 수의 최대 연속 과 뒤의 n - i 개의 최대 연속 과 더 불어 요구 하 는 결과 라 도.
뒤의 n - i 개의 최대 연속 과 거꾸로 유도 해 야 합 니 다.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
const int MAXN = 50010;
int an[MAXN];
int d1[MAXN], d2[MAXN];
int main()
{
int cases;
scanf("%d", &cases);
while (cases--)
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &an[i]);
int tmax = INT_MIN, temp = 0;
for (int i = 1; i <= n; ++i)
{
temp += an[i];
if (tmax < temp)
tmax = temp;
if (temp < 0)
temp = 0;
d1[i] = tmax;
}
tmax = INT_MIN, temp = 0;
for (int i = n; i >= 1; --i)
{
temp += an[i];
if (tmax < temp)
tmax = temp;
if (temp < 0)
temp = 0;
d2[i] = tmax;
}
int ans = INT_MIN;
for (int i = 1; i < n; ++i)
if (ans < d1[i] + d2[i+1])
ans = d1[i] + d2[i+1];
printf("%d
", ans);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
