UVa-1347 -Tour(DP)

1647 단어 OJ 시리즈. - UVa.동적 기획최단로
제목: 2차원 평면의 n개의 좌표를 정한 다음에 선로를 찾아 가장 왼쪽의 점에서 출발한 다음에 가장 오른쪽의 점으로 돌아간다. 기점과 종점의 점만 두 번 지나갈 수 있다.최단로를 찾다.
문제풀이: 걸어서 돌아오면 같은 점을 거치지 않고 두 사람이 각각 두 갈래 길을 걸어서 종점에 도달할 수 있다. dp[i][j]로 두 사람이 가장 멀리 max(i, j)까지 가는 상황을 나타낸다. 그러면 다음 결정은 누가 다음 지점에 가는지 보는 것이다. 즉, d[i][j]=min(dp[i+1][j]+dist[j][j]][j]], dp[i+1][i][i]+dist[i]+dist[j][j][i+1])이다. 틀림없이 한 사람이 두 번째 지점에 도착하고 두 번째 n-1에 도착할 때이다.즉 dp[n-1][j]=dist[n-1][n]+dist[j][n],ans=dp[2][1]+dist[2][1]이다.
AC 코드:
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1e3+7;
#define _for(i,a,b) for(int i=a;i<=b;i++)
struct node
{
    int x,y;
}a[maxn];
int n;
double dp[maxn][maxn],dist[maxn][maxn];
double length(int p,int q)
{
    double s = (double)(a[p].x-a[q].x)*(double)(a[p].x-a[q].x)+(double)(a[p].y-a[q].y)*(double)(a[p].y-a[q].y);
    return sqrt(s);
}
int main(int argc, char const *argv[])
{
    while(cin>>n)
    {
        memset(dist,sizeof(dist),0);
        memset(dp,sizeof(dp),0);
        _for(i,1,n)cin>>a[i].x>>a[i].y;
        _for(i,1,n)
        {
            _for(j,1,n)
            {
                dist[i][j]=length(i,j);
               // cout<1;i--)
        {
            _for(j,1,i-1)
            {
                if(i==n-1)dp[i][j]=dist[i][n]+dist[j][n];
                else dp[i][j] = min(dp[i+1][i]+dist[j][i+1],dp[i+1][j]+dist[i][i+1]);
            }
        }
        printf("%.2lf
",dp[2][1]+dist[2][1]);
    }
    return 0;
}
동적 dp 학습 소기
WSL 시작

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage