POJ 1036 Gansters (DP)
20958 단어 poj
사고방식: 전형적인 동적 기획은 dp[t][k]로 t시간의 문 넓이가 k일 때의 최대 수입을 기록한다. 이 값은 dp[t-1][]와만 관련이 있기 때문에 스크롤 그룹으로 실현할 수 있다. 그렇지 않으면 메모리를 초과할 수 있다. 또한 깡패를 저장할 때 struct를 이용하여 저장한다. 그렇지 않으면 메모리가 부족하다. 그리고 초기화된 문제도 있다. t시간(t
#include
<
iostream
>
#include
<
cstdio
>
#include
<
algorithm
>
#include
<
memory.h
>
#include
<
cmath
>
#include
<
bitset
>
#include
<
vector
>
using
namespace
std;
const
int
BORDER
=
(
1
<<
26
)
-
1
;
const
int
MAXSIZE
=
37
;
const
int
MAXN
=
110
;
const
int
INF
=
0x6ffffff
;
#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)
typedef
struct
{
int
stout,pros;
int
next;
}Edge;
Edge edge[MAXN];
int
pros[MAXN],dp[
2
][
30005
],come[MAXN],stout[MAXN];
int
net[
30005
];
int
con,N,T,K,index;
void
add_edge(
const
int
&
u,
const
int
&
st,
const
int
&
pr)
{
edge[index].stout
=
st;
edge[index].pros
=
pr;
edge[index].next
=
net[u];
net[u]
=
index;
++
index;
}
int
get_pros(
const
int
&
tim,
const
int
&
stout)
{
int
sum
=
0
;
for
(
int
i
=
net[tim]; i
!=
-
1
; i
=
edge[i].next)
if
(edge[i].stout
==
stout)
sum
+=
edge[i].pros;
return
sum;
}
int
init()
{
con
=
0
;
index
=
0
;
CLR(net,
-
1
);
CLR(dp,
0
);
return
0
;
}
int
input()
{
int
i,j,tmp;
for
(i
=
0
; i
<
N;
++
i)
IN(come[i]);
for
(i
=
0
; i
<
N;
++
i)
IN(pros[i]);
for
(i
=
0
; i
<
N;
++
i)
IN(stout[i]);
for
(i
=
0
; i
<
N;
++
i)
add_edge(come[i],stout[i],pros[i]);
return
0
;
}
int
_dp()
{
int
i,j,tmp,n_door;
for
(i
=
1
; i
<=
T;
++
i)
{
n_door
=
MIN(i,K);
dp[con][
0
]
=
MAX(dp[
1
-
con][
0
],dp[
1
-
con][
1
]);
dp[con][n_door]
=
MAX(dp[
1
-
con][n_door],dp[
1
-
con][n_door
-
1
]);
dp[con][n_door]
+=
get_pros(i,n_door);;
for
(j
=
1
; j
<
n_door;
++
j)
{
tmp
=
MAX(dp[
1
-
con][j
-
1
],dp[
1
-
con][j]);
dp[con][j]
=
MAX(tmp,dp[
1
-
con][j
+
1
]);
tmp
=
0
;
dp[con][j]
+=
get_pros(i,j);
}
memcpy(dp[
1
-
con],dp[con],
sizeof
(come));
con
=
1
-
con;
}
return
0
;
}
int
work()
{
int
i,j,tmp;
_dp();
tmp
=
0
;
for
(i
=
0
; i
<=
K;
++
i)
tmp
=
MAX(tmp,dp[con][i]);
OUT(tmp);
return
0
;
}
int
main()
{
while
(scanf(
"
%d%d%d
"
,
&
N,
&
K,
&
T)
!=
EOF)
{
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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
