POJ 3925 - 상태 DP.비트 연산
한 종류의 점 개수가 n=15 정도인 문제에 대해...상태 DP를 민감하게 연상해야 하는데...n비트 2진수로 비교적 좋은 모든 점의 상태에서...이 문제는 바로 이렇다..x(0<=x<=2^n)로 현재 나무에 어떤 점이 있는지 표시...
여기 두 자리 연산이 들어갔는데...
하나는 십진수 x가 이진수 아래의 k위가 1인지 아닌지를 판단하는 것이다.x&(1<
사실 쓰고 나서...본질적으로 매거점을 최소화해서 트리를 만드는 게 저랑 같은 상태인 DP랑 똑같아요...왜냐하면 제가 업데이트 과정에서 프라임의 과정이었기 때문에...
Program:
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<map>
#include<queue>
#include<stack>
#define ll long long
#define oo 1000000000
#define pi acos(-1)
using namespace std;
int n,m,p[20],arc[20][20],g,ans,dp[40000];
double minimal;
int main()
{
int i,x,y,k,w,z,v;
while (~scanf("%d%d",&n,&m))
{
if (!n && !m) break;
for (i=1;i<=n;i++) scanf("%d",&p[i]);
for (y=1;y<=n;y++)
for (x=1;x<=n;x++)
scanf("%d",&arc[y][x]);
g=(1<<n)-1;
memset(dp,-1,sizeof(dp));
dp[0]=0;
minimal=1e+20;
for (x=1;x<=g;x++)
{
v=0;
for (k=1;k<=n;k++)
if (x & (1<<k-1)) // k 1
{
v+=p[k];
w=x-(1<<k-1);
for (y=1;y<=n;y++)
if (w & (1<<y-1))
if (dp[x]==-1 || dp[x]>dp[w]+arc[y][k])
dp[x]=dp[w]+arc[y][k];
}
k=0;
z=x;
while (z)
{
k++;
z=z & (z-1);
} // ..
if (k==m && minimal>(dp[x]*1.0/v))
{
minimal=dp[x]*1.0/v;
ans=x;
}
}
for (x=1;x<=n;x++)
if (ans & (1<<x-1)) printf("%d ",x);
printf("
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
ExtJS의 onRender 및 renderThe control structure (inversion of control) that is the result of the application of a template pattern is often referr...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
