백 련 / 2018 빅 데이터 연구 센터 여름 캠프 탑승 시험 D: 달리기
3561 단어 백 련 OJ/poj
D: 달리기
총 시간 제한: 1000ms 메모리 제한: 65536kB
묘사 하 다.
젖소 들 은 운동 을 통 해 자신의 운동 세 포 를 키 울 계획 이다. 그 중 한 명 으로 베 시가 선택 한 운동 방식 은 매일 N (1 & lt; N & gt; = 10, 000) 분간 조깅 을 하 는 것 이다.베 시 는 매 분 마다 달리 기 를 할 지 쉬 는 지 를 선택한다.베 시의 체력 은 그녀의 달리기 거 리 를 제한 했다.더 구체 적 으로 베 시가 i 분 안에 달리 기 를 선택한다 면 그녀 는 1 분 안에 D 를 뛸 수 있다.i (1 < = D i < = 1, 000) 미터, 그리고 그녀의 피로 도 는 1 증가 합 니 다.하지만 언제나 베 시의 피로 도 는 M (1 & lt; = M & gt; = 500) 을 넘 어 서 는 안 된다.베 시가 휴식 을 선택한다 면, 그녀의 피로 도 는 분당 1 씩 줄 어 들 지만, 그녀 는 피로 도가 0 으로 회 복 될 때 까지 쉬어 야 한다.피로 도가 0 일 때 쉬 면 피로 도 는 변동 이 없다.조깅 을 시작 할 때 베 시의 피로 도 는 0 이 었 다.그리고 N 분 의 운동 이 끝 날 때 베 시의 피로 도 는 0 으로 회복 해 야 한다. 그렇지 않 으 면 하루 종일 남 은 일 에 대처 할 충분 한 정력 이 없 을 것 이다.베 시 는 최대 몇 미 터 를 뛸 수 있 는 지 계산 해 보 세 요.
입력
첫 번 째 줄: 두 번 째 칸 으로 구 분 된 정수: N 과 M 두 번 째 줄. N + 1 줄: i + 1 은 1 개의 정수: Di
출력
첫 번 째 줄: 1 개의 정 수 를 출력 하여 모든 제한 조건 을 만족 시 키 는 상황 에서 베 시가 뛸 수 있 는 최대 거 리 를 나타 낸다.
샘플 입력
5 2
5
3
4
2
10샘플 출력
9제시 하 다.
30% 의 데이터 에 대해 N < = 50, M < = 10
근원
USACO 2008 January Silver
--------------------------------------------------------------
사고의 방향
동적 계획
f [i] [j]: i 분 의 피로 도 는 j 시 달리기 의 거리 이다. 만약 에 i 분 의 피로 도 j 가 도달 하지 못 하거나 이때 휴식 중 피로 도가 0 으로 회복 되 지 않 으 면 f [i] [j] = - 1
밀 어 붙 일 때 달리기 와 휴식 두 가지 상황 에 대해 토론 한다. "베 시가 휴식 을 선택한다 면 그녀의 피로 도 는 분당 1 씩 줄 어 들 지만 피로 도가 0 으로 회 복 될 때 까지 쉬어 야 한다" 는 말 에 주의해 야 한다.
-----------------------------------------------------
코드
#include
#include
using namespace std;
const int NMAX = 10010, MMAX = 505;
int a[NMAX] = {};
int f[NMAX][MMAX] = {}; // i j , i （ ）,f[i][j] = -1
int main()
{
#ifndef ONLINE_JUDGE
ifstream fin ("D.txt");
int n,m,i,j;
fin >> n >> m;
for (i=1; i<=n; i++)
{
fin >> a[i];
}
fin.close();
for (i=0; i=0)
{
if (j0)
{
if (f[i-1][j] + a[i] > f[i][j+1])
f[i][j+1] = f[i-1][j] + a[i]; // i
if (i-1+j <= n && f[i-1][j] > f[i-1+j][0])
f[i-1+j][0] = f[i-1][j]; // i i-1+j
}
else if (j==m)
{
if (i-1+m <= n && f[i-1][j] > f[i][j-1])
f[i-1+m][0] = f[i-1][j]; // m
}
else if (j==0)
{
if (f[i-1][0] + a[i] > f[i][1])
f[i][1] = f[i-1][0] + a[i]; // i
if (f[i-1][0] > f[i][0])
f[i][0] = f[i-1][0]; // 0
}
}
}
}
cout << f[n][0];
return 0;
#endif
#ifdef ONLINE_JUDGE
int n,m,i,j;
cin >> n >> m;
for (i=1; i<=n; i++)
{
cin >> a[i];
}
for (i=0; i=0)
{
if (j0)
{
if (f[i-1][j] + a[i] > f[i][j+1])
f[i][j+1] = f[i-1][j] + a[i]; // i
if (i-1+j <= n && f[i-1][j] > f[i-1+j][0])
f[i-1+j][0] = f[i-1][j]; // i i-1+j
}
else if (j==m)
{
if (i-1+m <= n && f[i-1][j] > f[i][j-1])
f[i-1+m][0] = f[i-1][j]; // m
}
else if (j==0)
{
if (f[i-1][0] + a[i] > f[i][1])
f[i][1] = f[i-1][0] + a[i]; // i
if (f[i-1][0] > f[i][0])
f[i][0] = f[i-1][0]; // 0
}
}
}
}
cout << f[n][0];
return 0;
#endif
} 좋은 웹페이지 즐겨찾기
