POJ1661Help Jimmy _dp
제목 모형을 물줄기의 하락으로 상상한다. 널빤지를 만난 후 두 줄기로 나뉘어 계속 아래로 내려가 언제 지면에 도착할 수 있느냐고 묻는다(지면이 마지막 널빤지라고 가정한다)
dp[i][0] 물이 i번째 널빤지 왼쪽 끝에 도달하는 가장 빠른 시간
dp[i][1] 오른쪽 끝
//poj1661
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[1100][2],N,MAX;
struct block{
int E[2],H;
}B[1100];
bool cmp(block a,block b){
return a.H>b.H;
}
int OK(int x,int S){
for(int i=S+1;i<=N+1;i++){
if(B[S].H-B[i].H>MAX) break;
if(B[i].E[0]<=x&&B[i].E[1]>=x)return i;
}
return 0;
}
int main()
{
int i,j,k,T;
scanf("%d",&T);
while(T--){
int x,y;
scanf("%d%d%d%d",&N,&x,&y,&MAX);
///////////////////////////////////////////////
B[0].E[0]=B[0].E[1]=x;B[0].H=y;
for(i=1;i<=N;i++) scanf("%d%d%d",&B[i].E[0],&B[i].E[1],&B[i].H);
B[N+1].E[0]=-30000;B[N+1].E[1]=30000;B[N+1].H=0;
sort(B+1,B+1+N,cmp);
/////////////////////////////////////////////////////////
for(i=1;i<=N+1;i++) dp[i][0]=dp[i][1]=1000000000;dp[0][0]=dp[0][1]=0;
int time,ans=1000000000;
for(i=0;i<=N;i++)
for(j=0;j<=1;j++){
k=OK(B[i].E[j],i);
if(k){
time=dp[i][j]+B[i].H-B[k].H;
if(k==N+1&&ans>time) ans=time;
for(int jj=0;jj<=1;jj++)
dp[k][jj]=min(dp[k][jj],time+abs(B[i].E[j]-B[k].E[jj]));
}
}
printf("%d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
