poj1925 (좌표의 dp)
1625 단어 dp
n개의 건축을 제시하고 각 건축은 두 개의 수로 x를 나타낸다. y는 x가 가로축에 있는 위치를 나타내고 y는 이 건축의 높이를 나타낸다.모든 건축물의 높이는 첫 번째 건축물의 높이보다 크다.모든 건물의 입력 순서는 x, y가 어릴 때부터 도착하는 순서에 따라 배열된다.
스파이더맨은 첫 번째 건물에서 마지막 건물로 여자친구를 구하러 간다.그는 매번 흔들릴 때마다 건축의 대칭에 관한 위치로 갔다.마지막 건물의 최소 흔들림 횟수를 구하다.
문제풀이 사고방식: 처음에는 쉽다고 생각했는데 dp[i]는 i번째 건물에 도착하는 최소 흔들림 횟수를 나타냈고 dp[i]=max(dp[k]+1), 결과는WA였다.다른 사람의 생각을 보고서야 이 문제를 내가 너무 간단하게 생각했다는 것을 알았다.WA 원인: 후효성 문제를 해결하지 못하고 k와 j가 있다고 가정하면 모두 dp[j]+1=dp[k]+1을 만족시키지만 두 위치가 진동하는 폭이 다르면 이후의 상태에 영향을 미친다.
그래서 이 문제의 정해는 dp[i]가 x축의 i 위치에 있을 때의 최소 진동 횟수를 나타낸다.상태 방정식은 변하지 않습니다.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 5005;
struct Node
{
__int64 x,y;
}building[maxn];
int n,dp[1000005];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i = 1; i <= n; i++)
scanf("%I64d%I64d",&building[i].x,&building[i].y);
memset(dp,-1,sizeof(dp));
dp[building[1].x] = 0;
for(int i = 2; i <= n; i++)
{
int dis = sqrt(building[i].y * building[i].y - (building[i].y - building[1].y) * (building[i].y - building[1].y) + 0.5);
for(int j = 1; j <= dis; j++) //dis i 。
{
if(building[i].x - j < building[1].x) break;
if(dp[building[i].x - j] == -1) continue;
int tmp = min(building[i].x + j,building[n].x);
if(dp[tmp] == -1) dp[tmp] = dp[building[i].x - j] + 1;
else dp[tmp] = min(dp[tmp],dp[building[i].x - j] + 1);
}
}
printf("%d
",dp[building[n].x]);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
