포병 진지
17511 단어 poj
2. 문제 풀이 사고방식: (1) N열을 확정한 상황에서 동업자가 충동이 생기지 않는 n중 가능(N<=10이기 때문에 n<=60);(2) 위에서 아래로 한 줄씩 왼쪽에서 오른쪽으로 한 줄씩 훑어본다. 그 중에서 dp[i][j][k]는 i줄을 나타낼 때, j는 i줄의 상태 상황을 나타낼 때, k는 i-1줄의 상태 상황에서 가능한 포병 배치 수량을 나타낸다.(3) 결과는 마지막 줄의 모든 상황에 대한 최대값이다.
3. 주의사항: 주의1<
#include
<
iostream
>
using
namespace
std;
int
status[
105
],judge[
66
];
int
num[
66
];
int
dp[
105
][
66
][
66
];
int
M,N,cnt;
inline
int
max(
int
p1,
int
p2)
{
return
p1
>
p2
?
p1:p2;
}
void
Init()
{
int
i,t,nn;
for
(i
=
0
;i
<
(
1
<<
N);i
++
)
{
nn
=
0
;
if
( ((i
<<
1
)
&
i)
||
((i
<<
2
)
&
i))
//
continue
;
judge[cnt]
=
i;
t
=
i;
while
(t)
{
if
(t
&
1
)
nn
++
;
t
=
(t
>>
1
);
}
num[cnt
++
]
=
nn;
}
}
void
DP()
{
int
i,j,k,ans;
for
(i
=
0
;i
<
M;i
++
)
{
for
(j
=
0
;j
<
cnt;j
++
)
{
if
((status[i]
&
judge[j])
!=
judge[j])
continue
;
if
(i
==
0
)
{
dp[i][j][
0
]
=
num[j];
continue
;
}
if
(i
==
1
)
{
for
(k
=
0
;k
<
cnt;k
++
)
{
if
(judge[j]
&
judge[k])
continue
;
dp[i][j][k]
=
max(dp[i][j][k],dp[i
-
1
][k][
0
]
+
num[j]);
}
continue
;
}
for
(k
=
0
;k
<
cnt;k
++
)
{
if
(judge[j]
&
judge[k])
continue
;
for
(
int
p
=
0
;p
<
cnt;p
++
)
{
if
(judge[k]
&
judge[p])
continue
;
if
( (judge[j]
&
judge[k])
||
(judge[j]
&
judge[p]))
continue
;
dp[i][j][k]
=
max(dp[i][j][k],dp[i
-
1
][k][p]
+
num[j]);
}
}
}
}
ans
=
0
;
for
(i
=
0
;i
<
cnt;i
++
)
for
(j
=
0
;j
<
cnt;j
++
)
if
(dp[M
-
1
][i][j]
>
ans)
ans
=
dp[M
-
1
][i][j];
cout
<<
ans
<<
endl;
}
int
main()
{
int
i,j,tmp;
char
ch;
scanf(
"
%d%d
"
,
&
M,
&
N);
for
(i
=
0
;i
<
M;i
++
)
{
getchar();
tmp
=
0
;
for
(j
=
N
-
1
;j
>=
0
;j
--
)
{
scanf(
"
%c
"
,
&
ch);
if
(ch
==
'
P
'
)
tmp
+=
(
1
<<
j);
}
status[i]
=
tmp;
}
Init();
DP();
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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
