POJ 2479 Maximum Sum (DP)
10970 단어 poj
사고방식: 먼저 왼쪽에서 오른쪽으로 dp를 구하고 한 단락의 연속 자열의 최대 합을 구한 다음에 오른쪽에서 왼쪽으로 dp를 구하여 두 단락의 연속 자열의 최대 합을 구한다. 방법은 여전히 고전적이다.
#include
<
iostream
>
#include
<
cstdio
>
#include
<
algorithm
>
#include
<
memory.h
>
#include
<
cmath
>
#include
<
bitset
>
#include
<
queue
>
#include
<
vector
>
using
namespace
std;
const
int
MAXN
=
100400
;
const
int
INF
=
0x4ffffff
;
#define
CLR(x,y) memset(x,y,sizeof(x))
#define
ADD(x) x=((x+1)&BORDER)
#define
IN(x) scanf("%d",&x)
#define
OUT(x) printf("%d
",x)
#define
MIN(m,v) (m)<(v)?(m):(v)
#define
MAX(m,v) (m)>(v)?(m):(v)
#define
ABS(x) ((x)>0?(x):-(x))
int
arr[MAXN],dp[MAXN];
int
sum,n,ans;
int
init()
{
sum
=
0
;
ans
=
-
INF;
CLR(dp,
0
);
return
0
;
}
int
input()
{
for
(
int
i
=
0
; i
<
n;
++
i)
IN(arr[i]);
return
0
;
}
int
work()
{
int
i,j,tmp;
tmp
=
-
INF;
for
(i
=
0
; i
<
n;
++
i)
{
sum
+=
arr[i];
tmp
=
MAX(tmp,sum);
dp[i]
=
tmp;
sum
=
MAX(sum,
0
);
}
sum
=
0
;
tmp
=
-
INF;
for
(i
=
n
-
1
; i
>
0
;
--
i)
{
sum
+=
arr[i];
tmp
=
MAX(sum,tmp);
sum
=
MAX(sum,
0
);
ans
=
MAX(tmp
+
dp[i
-
1
],ans);
}
OUT(ans);
return
0
;
}
int
main()
{
int
tt;
while
(IN(n))
{
if
(
!
n)
break
;
init();
input();
work();
}
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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
