2018.07.18 로곡P1171 판매원의 난제(상압dp)

2814 단어 #상압

전송문 느낌은 고전적인 상압 dp로 카드 상수를 아무렇게나 썼고 O(2)O(2)를 열어 물을 최적화시켰다...나는 직접 dp[i][j]dp[i][j]로 현재 i번째 점에 있고 현재 점의 선택 상황은 j(이진법으로 상태를 표시한다)를 나타낸다.이렇게 하면 직접위 연산자는 앞으로 갈 수 있는 점을 들고 상태를 옮긴다.경계는 모든 점이 한 번 빼앗겼다.코드는 다음과 같습니다.

#include
using namespace std;
int dp[21][1050000],dis[25][25],n;
inline int min(int a,int b){return aint dfs(int p,int state){
    if(dp[p][state]!=0x3f3f3f3f)return dp[p][state];
    if(state==(1<1)return dp[p][state]=dis[p][1];
    for(int i=1;i<=n;++i)if(((1<1))&state)==0)dp[p][state]=min(dp[p][state],dis[p][i]+dfs(i,state|(1<1))));
    return dp[p][state];
}
int main(){
    memset(dp,0x3f,sizeof(dp));
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            scanf("%d",&dis[i][j]);
    printf("%d",dfs(1,1));
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Rails Turbolinks를 페이지 단위로 비활성화하는 방법

원래 Turobolinks란? Turbolinks는 링크를 생성하는 요소인 a 요소의 클릭을 후크로 하고, 이동한 페이지를 Ajax에서 가져옵니다. 그 후, 취득 페이지의 데이터가 천이 전의 페이지와 동일한 것이 있...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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