집합 상의 동적 계획 - 최 적 화 된 배합 문제 (추천: * * * *)
/*
:
《 》, ---
: n P0,P1,...,Pn-1, n/2 (n ), 。 。
:d(i,S) i , S
:d(i,S)=min{|PiPj|+d(i-1,S-{i}-{j}}
,
: ,i S ,S 1 i, , n-1 0 , , 2。 , 。
: , n , , 。
:① , , 。
*/
// : 。。。
#include <cstdio>
#include <cstring>
#include <cmath>
const int nMax=21;
const double INF=1e10;
int n;
struct Node
{
int x,y,z;
}node[nMax];
double d[nMax][1<<nMax];
void init()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d %d %d",&node[i].x,&node[i].y,&node[i].z);
}
double min(double a,double b)
{
return a<b?a:b;
}
double dis(Node &a,Node &b)//①
{
return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
void solve()
{
for(int i=0;i<n;i++)
{
for(int s=0;s<(1<<(i+1));s++)
{
if(s==0) d[i][s]=0;
else d[i][s]=INF;
if((s & (1<<i)))
{
for(int j=i-1;j>=0;j--)
if((s & (1<<j)))
d[i][s]=min(d[i][s],dis(node[i],node[j])+d[i-1][s^(1<<i)^(1<<j)]);
}
else if(i!=0)
{
d[i][s]=d[i-1][s];
}
}
}
}
int main()
{
freopen("f://data.in","r",stdin);
init();
solve();
printf("%.3lf
",d[n-1][(1<<n)-1]);
return 0;
}
// : 。。。
//#define TEST
#include <cstdio>
#include <cstring>
#include <cmath>
const int nMax=21;
const double INF=1e10;
int n,S;
struct Node
{
int x,y,z;
}node[nMax];
double d[1<<nMax];
void init()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d %d %d",&node[i].x,&node[i].y,&node[i].z);
S=1<<n;
for(int i=1;i<S;i++)
d[i]=-1;
d[0]=0;
}
double min(double a,double b)
{
return a<b?a:b;
}
double dis(Node &a,Node &b)
{
return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
double dp(int p)
{
if(d[p]!=-1) return d[p];
d[p]=INF;
int i,j;
for(i=n-1;i>=0;i--)
if(p & (1<<i))
break;
for(j=i-1;j>=0;j--)
if(p & (1<<j))
d[p]=min(d[p],dis(node[i],node[j])+dp(p^(1<<i)^(1<<j)));
#ifdef TEST
printf("%d %d
",p,d[p]);
#endif
return d[p];
}
int main()
{
freopen("f://data.in","r",stdin);
init();
printf("%.3lf
",dp(S-1));
return 0;
}
// :
#include <cstdio>
#include <cstring>
#include <cmath>
const int nMax=21;
const double INF=1e10;
int n,S;
struct Node
{
int x,y,z;
}node[nMax];
double d[1<<nMax];
void init()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d %d %d",&node[i].x,&node[i].y,&node[i].z);
S=1<<n;
d[0]=0;
}
double min(double a,double b)
{
return a<b?a:b;
}
double dis(Node &a,Node &b)
{
return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
void solve()
{
for(int s=1;s<S;s++)
{
int i,j;
d[s]=INF;
for(i=n-1;i>=0;i--)
if(s & 1<<i)
break;
for(j=i-1;j>=0;j--)
if(s & 1<<j)
d[s]=min(d[s],dis(node[i],node[j])+d[s^(1<<i)^(1<<j)]);
}
}
int main()
{
freopen("f://data.in","r",stdin);
init();
solve();
printf("%.3lf
",d[S-1]);
return 0;
}
테스트 데이터:
Input: 20 1 2 3 1 1 1 5 6 2 4 7 8 2 3 1 1 4 7 2 5 8 3 6 9 1 2 5 2 3 6 4 5 2 7 8 5 4 5 1 -1 2 3 -1 -9 -7 0 0 0 100 0 0 9 5 1 7 5 3 5 5 5 Output: 119.076
참고 블 로그:http://www.cppblog.com/rakerichard/archive/2010/02/11/107696.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.