P1523 여행사 약식
중국어 문제는 이해하기 쉽지만 잘 풀지 못해, 짜증나!!!문제풀이를 보고 서쪽에서 동쪽으로 가는 것과 동쪽에서 서쪽으로 가는 것은 서쪽에서 서쪽으로 가는 것으로 볼 수 있다. 우리가 한 점에 가서 다른 점으로 갈 때 자연스럽게 dp가 생각난다. 왜냐하면 이 점에서 다른 점으로 가는 것은 두 가지 길 중 하나를 선택해서 가는 것이기 때문이다. dp[i][j]는 첫 번째 길이 i로 가고 두 번째 길이 j로 가기 때문에 j>i를 규정하면 방정식을 옮길 수 있다.
dp[i][j+1]=min(dp[i][j+1],dp[i][j]+dis(j,j+1));// j+1
dp[j][j+1]=min(dp[j][j+1],dp[i][j]+dis(i,j+1));// j+1, , dp[j][j+1]。
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define ms(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x & -x
#define fi first
#define se second
#define bug cout<
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
using namespace std;
const int maxn = 1e3 + 5;
const int maxm = 1.5e5+50;
const double eps = 1e-7;
const double inf = 0x3f3f3f3f;
const double lnf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const double pi=3.141592653589;
struct node
{
double l,r;
}a[maxn];
double dp[maxn][maxn],b[maxn];
bool cmp(node A,node B)
{
return A.l<B.l;
}
double dis(int x,int y)
{
return sqrt((a[x].l-a[y].l)*(a[x].l-a[y].l)+(a[x].r-a[y].r)*(a[x].r-a[y].r));
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&a[i].l,&a[i].r);
}
ms(dp,lnf);
sort(a+1,a+1+n,cmp);
dp[1][2]=dis(1,2);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=1e30;
}
}
dp[1][2]=dis(1,2);
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
dp[i][j+1]=min(dp[i][j+1],dp[i][j]+dis(j,j+1));
dp[j][j+1]=min(dp[j][j+1],dp[i][j]+dis(i,j+1));
}
}
double ans=1e30;
for(int i=3;i<=n;i++)
{
ans=min(ans,dp[i][n]+dis(i,n));
}
printf("%.2lf
",ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
P4017 최대 먹이사슬 계수(간단한 나무 dp)P4017 최대 먹이사슬 개수 데이터에 고리가 존재하지 않기 때문에 반드시 먹이사슬의 시작점을 찾을 수 있다. 그러면 먹이사슬의 시작점을 기억화하여 검색한 다음에 끝점까지 1로 되돌아갈 수 있다. 이는 먹이사슬이 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.