Codeforces Round \ # 174 (Div. 1) B. Cow 프로그램 (dp + 기억 화)
1364 단어 codeforces
사고방식: dp [now] [flag] 는 현재 위치 now 를 표시 하고 flag 는 다음 에 해 야 할 절 차 를 표시 한 다음 에 제목 의 기억 화 에 따라 기억 을 검색 하고 vis 배열 은 이미 방문 한 상 태 를 표시 합 니 다.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std;
const int MAX_N = (200000 + 100);
long long dp[MAX_N][2];
int vis[MAX_N][2];
int N, a[MAX_N];
long long dfs(int now, int dir)
{
if (now <= 0 || now > N) return 0;
if (~dp[now][dir]) return dp[now][dir];
if (vis[now][dir]) return -1;
vis[now][dir] = 1;
long long res = dfs(dir ? now + a[now] : now - a[now], dir ^ 1);
return dp[now][dir] = (res < 0 ? -1 : res + a[now]);
}
int main()
{
while (cin >> N) {
FOR(i, 2, N) cin >> a[i];
memset(dp, -1, sizeof(dp));
memset(vis, 0, sizeof(vis));
FOR(i, 1, N - 1) {
long long ans = dfs(i + 1, 0);
cout << (ans < 0 ? -1 : ans + i) << endl;
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
