[UVA 1632] Alibaba[구간 DP]
주제 분석:
n개의 보물이 있고, 각각 한 위치에 p[i]가 있으며, 정해진 시간에 t[i]는 사라집니다.알리바바는 보물이 사라지기 전에 모든 보물을 수집하고 방법이 있느냐고 물었다.있으면 최소 몇 초?
문제 해결 방법:
뭐, 보물을 찾는 것은 틀림없이 연속적인 구간을 모두 제거하는 것이고, 고의로 가지지 않는 것은 절대 최선의 전략이 아니다.그래서 전체 전략은 두 가지를 포함한다. 왼쪽으로 가든지 오른쪽으로 가든지.상태를 dp[l][r][2]로 설정합니다.0은 알리바바가 왼쪽에 있고 1은 알리바바가 오른쪽에 있다.전체적인 의미는 이 구간을 얻는 데 필요한 최소한의 시간이라는 것이다.다음은 이동을 분석하고 왼쪽 단점(오른쪽 단점 유사), dp[l][r][0]=min(dp[l+1][r][0]+p[l+1]-p[l], dp[l+1][r][1]+p[r]-p[l])를 단독으로 분석한다.이전 구간에서 왼쪽으로 걸어왔거나, 이전 구간에서 오른쪽으로 걸어왔다.
바로 dp[l][r][i]는 이 상태에 도달하는 시간을 대표하기 때문에 다시 갱신한 후에 갱신 후의 최소 시간과 규정된 시간을 비교한 다음에 초과하면 오랫동안 부여된 값은 INF이다.
갱신할 때 동네 값을 사용했기 때문에 이 문제는 갱신할 때 동네에서 큰 동네로 갱신합니다.전체 순환의 순서도 확정되었다.
개인적인 느낌:
두 번째로 이 문제를 풀었다.어렴풋이 상태가 3차원이라는 것만 기억한다.반나절 동안 카드가 시간을 어떻게 표시하는지 생각하면 내가 분명히 dp로 시간을 구하려고 했는데 보물을 얻을 수 있는지 없는지를 생각할 시간을 가져야 한다는 모순감을 느낀다. 에이~ 다시 하는 장점이 나타난다.이번에 또 이해가 깊어졌다.
구체적인 코드는 다음과 같습니다.
#include<iostream>
#include<cstdio>
using namespace std;
const int INF = 0x7f7f7f7f, MAXN = 1e4 + 111;
int p[MAXN], t[MAXN], n, dp[MAXN][MAXN][2];
int main()
{
while(~scanf("%d", &n))
{
for (int i = 1; i <= n; ++i)
scanf("%d%d", &p[i], &t[i]);
int ans, cur;
for (int i = n; i >= 1; --i)
for (int j = i + 1; j <= n; ++j)
{
dp[i][j][0] = min(dp[i + 1][j][0] + p[i + 1] - p[i],
dp[i + 1][j][1] + p[j] - p[i]);
if (dp[i][j][0] >= t[i]) dp[i][j][0] = INF;
dp[i][j][1] = min(dp[i][j - 1][0] + p[j] - p[i],
dp[i][j - 1][1] + p[j] - p[j - 1]);
if (dp[i][j][1] >= t[j]) dp[i][j][1] = INF;
}
ans = min(dp[1][n][0], dp[1][n][1]);
if (ans == INF) cout << "No solution
";
else cout << ans << '
';
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
