POJ 1179 Polygon (DP)
16638 단어 poj
이 문제는 매트릭스 체인 상승의 변체로 dp로 하면 되지만 두 음수 상승도 가장 클 수 있으니 한 상태의 최대수와 최소수를 모두 기억하고 마지막으로 최대수를 찾으면 된다.
#include
<
iostream
>
#include
<
cstdio
>
#include
<
memory.h
>
using
namespace
std;
#define
MAXN 100
struct
Node{
int
mmax;
int
mmin;
}f[MAXN][MAXN];
int
func(
const
int
&
a,
const
int
&
b,
const
char
&
o)
{
if
(o
==
'
t
'
)
return
a
+
b;
else
return
a
*
b;
}
int
main()
{
char
op[MAXN];
int
arr[MAXN];
int
n,i,j,mmin,mmax,k,h,tmp,st,en,mid1,mid2,mark_pos;
while
(scanf(
"
%d
"
,
&
n)
!=
EOF)
{
for
(i
=
0
;i
<
n;
++
i)
{
getchar();
op[i]
=
getchar();
scanf(
"
%d
"
,
&
arr[i]);
}
for
(i
=
0
;i
<
n;
++
i)
{
f[i][i].mmax
=
arr[i];
f[i][i].mmin
=
arr[i];
}
for
(k
=
1
;k
<
n;
++
k)
for
(i
=
0
;i
<
n;
++
i)
{
mmin
=
1
<<
30
;
mmax
=
-
mmin;
en
=
(i
+
k)
%
n;
for
(j
=
0
;j
<
k;
++
j)
{
mid1
=
(i
+
j)
%
n;
mid2
=
(i
+
j
+
1
)
%
n;
tmp
=
func(f[i][mid1].mmin,f[mid2][en].mmin,op[mid2]);
mmax
=
mmax
>
tmp
?
mmax:tmp;
tmp
=
func(f[i][mid1].mmax,f[mid2][en].mmax,op[mid2]);
mmax
=
mmax
>
tmp
?
mmax:tmp;
tmp
=
func(f[i][mid1].mmin,f[mid2][en].mmax,op[mid2]);
mmin
=
mmin
<
tmp
?
mmin:tmp;
tmp
=
func(f[i][mid1].mmax,f[mid2][en].mmin,op[mid2]);
mmin
=
mmin
<
tmp
?
mmin:tmp;
}
f[i][en].mmax
=
mmax;
f[i][en].mmin
=
mmin;
}
mmax
=
-
(
1
<<
30
);
for
(i
=
0
;i
<
n;
++
i)
{
en
=
(i
+
n
-
1
)
%
n;
if
(mmax
<
f[i][en].mmax)
{
mark_pos
=
i;
mmax
=
f[i][en].mmax;
}
}
printf(
"
%d
"
,mmax);
int
flag
=
0
;
for
(i
=
0
;i
<
n;
++
i)
{
if
(f[i][(i
+
n
-
1
)
%
n].mmax
==
mmax)
{
if
(
!
flag)
{
flag
=
1
;
printf(
"
%d
"
,i
+
1
);
}
else
printf(
"
%d
"
,i
+
1
);
}
}
printf(
"
"
);
}
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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
