2014년 바이두의 별 프로그램 설계 대회 - 퀄리파잉 레이스 1002 Disk Schedule(이중 유클리드 여행사 문제)
2985 단어 schedule
Input에서 입력한 첫 번째 행에는 테스트 데이터의 그룹 수를 나타내는 정수 M(0
이 문제는 유클리드 여행사의 문제 사상과 똑같다. 한 점에서 출발하여 매 점에 반복하지 않고 마지막에 기점에 도달하여 가장 짧은 거리를 구한다.
현재 배운 이것, 참고:
http://www.cppblog.com/doer-xee/archive/2009/11/30/102296.html
http://www.cnblogs.com/-sunshine/archive/2012/07/23/2605251.html
http://blog.csdn.net/xiajun07061225/article/details/8092247
코드:
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=1010;
const int inf=0x7fffffff;
int cas;
int n;
struct Node
{
int t,s;
}node[maxn];
double dp[maxn][maxn];
int dis(Node a,Node b)// ( + )
{
int ci=abs(a.t-b.t)*400;
int MAX=(a.s>b.s?a.s:b.s);
int MIN=(a.s<b.s?a.s:b.s);
int shan=min(MAX-MIN,360-MAX+MIN);
return ci+shan;
}
int DP(int n)//
{
dp[1][2]=dis(node[1],node[2]);
for(int j=3;j<=n;j++)
{
for(int i=1;i<=j-2;i++)
dp[i][j]=dp[i][j-1]+dis(node[j-1],node[j]);
dp[j-1][j]=inf;
for(int k=1;k<=j-2;k++)
{
int temp=dp[k][j-1]+dis(node[k],node[j]);
if(temp<dp[j-1][j])
dp[j-1][j]=temp;
}
}
dp[n][n]=dp[n-1][n]+dis(node[n-1],node[n]);
return dp[n][n];
}
int main()
{
cin>>cas;
while(cas--)
{
cin>>n;
node[1].t=0,node[1].s=0;
for(int i=1;i<=n;i++)
cin>>node[i+1].t>>node[i+1].s;
n++;
cout<<DP(n)+10*(n-1)<<endl;//
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
SpringBoot Schedule 구성 상세 정보1. 정시 임무 실현 방식 정시 작업 실현 방식: 자바 자체의 자바.util.Timer 클래스, 이 클래스는java를 조정할 수 있습니다.util.TimerTask 작업.이런 방식을 사용하면 프로그램이 특정한 주파수...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.