POJ2228 Naptime(원형 구조의 dp)
1448 단어 dp
제목: 하루에 n시간으로 구성되어 있으며, i시간에 잠을 자면 Ui점 체력을 회복할 수 있다.소 한 마리가 b시간을 쉬어야 하기 때문에 연속하지 않아도 되지만 쉬는 1시간은 체력을 회복할 수 없다.전날 마지막 시간과 이튿날 첫 시간은 이어져 이 소가 회복할 수 있는 체력 최대치를 구한다.
분석: P295-297.
코드:
#include
#include
#include
#include
using namespace std;
const int N = 4000, M = 4000;
int n, m, f[2][M][2], w[N], ans;
int main (){
scanf ("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
scanf ("%d", &w[i]);
if (m == 0)
{ printf ("0"); exit (0); }
memset (f, 0x80, sizeof f);
f[1 & 1][0][0] = 0;
f[1 & 1][1][1] = 0;
for (int i = 2; i <= n; i ++)
for (int j = 0; j <= m; j ++)
{
f[i & 1][j][0] = max (f[(i - 1) & 1][j][0], f[(i - 1) & 1][j][1]);
if (j - 1 >= 0) f[i & 1][j][1] = max (f[(i - 1) & 1][j - 1][0], f[(i - 1) & 1][j - 1][1] + w[i]);
}
ans = max (f[n & 1][m][1], f[n & 1][m][0]);
memset (f, 0x80, sizeof f);
f[1 & 1][1][1] = w[1];
for (int i = 2; i <= n; i ++)
for (int j = 0; j <= m; j ++)
{
f[i & 1][j][0] = max (f[(i - 1) & 1][j][0], f[(i - 1) & 1][j][1]);
if (j - 1 >= 0) f[i & 1][j][1] = max (f[(i - 1) & 1][j - 1][0], f[(i - 1) & 1][j - 1][1] + w[i]);
}
ans = max (ans, f[n & 1][m][1]);
printf ("%d", ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
