poj 3661 Running (dp)
n, m, n은 n분이 있음을 나타낸다. i분마다 대응하는 것은 i분마다 뛸 수 있는 거리이다. m는 최대 피로도를 나타낸다. 1분마다 뛸 때 피로도 +1, 피로도 ==m는 반드시 쉬어야 한다. 임의의 시간에 휴식을 선택할 수 있다. 만약에 휴식을 선택한다면 피로도 0까지 쉬어야 한다. 물론 피로도가 0일 때도 계속 휴식을 선택할 수 있다. n분 후에 피로도가 0이 뛸 수 있는 최대 거리를 구한다.
문제 풀이:
상태: dp[i][j] i분 피로도가 j일 때 걷는 최대 거리
주의: 상황에 따라 토론한다.
/*
：
dp[i][j] “ ” ， ！ ！
*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
typedef long long lld;
#define oo 0x3f3f3f3f
#define maxn 10000+5
#define maxm 500+5
int dp[maxn][maxm];
int d[maxn];
int main()
{
int n,m;
while(scanf("%d %d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d",&d[i]);
memset(dp,-1,sizeof dp);
dp[1][0]=0;
dp[1][1]=d[1];
for(int i=1;i<n;i++)
{
for(int j=0;j<=m;j++)
{
if(dp[i][j]==-1) continue;
if(j+1<=m)
dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+d[i+1]);
if(j==0)
dp[i+1][0]=max(dp[i+1][0],dp[i][0]);
if(0<j&&i+j<=n)
dp[i+j][0]=max(dp[i+j][0],dp[i][j]);
}
}
printf("%d
",dp[n][0]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
