글 읽기 - UVA104번 질문 드립니다.

hijigoo 7년 전 0

여기다가 질문을 드려도 될 지 모르겠지만 혹시 푸신 분이 있을까해서 글 남깁니다.

UV 104 번 답을 찾아보니

이렇게 되어있는데요

마지막 루프에서

for(j=0; j<N; j++){
double tmp = best[i][k][steps-1] * best[k][j][0];
if (tmp > best[i][j][steps]){
best[i][j][steps] = tmp;
path[i][j][steps] = k;
}
}

k 가 i 나 j일 때는 steps가 증가하면 안되는 것 아닌가요?

k가 i나 j일 떄 어떻게 동작하는지 이해가 안되네요..

Skip to content
Personal Open source Business Explore
Sign upSign inPricingBlogSupport
This repository
Search
 Watch 5  Star 7  Fork 12 SITZ/UVa
 Code  Issues 0  Pull requests 0  Projects 0  Pulse  Graphs
Branch: master Find file Copy pathUVa/104.cpp
7c52f3d  on 5 Jul 2011
@SITZ SITZ v1.0
1 contributor
RawBlameHistory     
85 lines (81 sloc)  3.04 KB
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

typedef unsigned int uint;
typedef long long int64;
typedef unsigned long long uint64;

using namespace std;

int main(){
    int N;    
    while(cin>>N){
                  double best[20][20][20];
                  int path[20][20][20];
                  int i, j, k, steps;
                  memset(best, 0, sizeof(double)*20*20*20);
                  for(i=0; i<N; i++){
                           for(j=0; j<N; j++){
                                    path[i][j][0] = i;
                                    if(i==j)
                                            best[i][j][0] = 1.0;
                                    else
                                        cin>>best[i][j][0];
                           }
                  }
                  bool stat=false;
                  for(steps=1; steps<N; steps++){
                            for(k=0; k<N; k++){
                                     for(i=0; i<N; i++){
                                              for(j=0; j<N; j++){
                                                       double tmp = best[i][k][steps-1] * best[k][j][0];
                                                       if (tmp > best[i][j][steps]){
                                                               best[i][j][steps] = tmp;
                                                               path[i][j][steps] = k;
                                                       }
                                              }
                                     }
                            }
                  }
                  for(steps=1; steps<N; steps++){
                  for(i=0; i<N; i++){
                           if(best[i][i][steps] > 1.01){
                                                int seq[steps];
                                                seq[steps]=path[i][i][steps];
                                                for(j=steps-1; j>=0; j--)
                                                      seq[j]=path[i][seq[j+1]][j];
                                                for(j=0;j<=steps;j++)
                                                      cout<<seq[j]+1<<" ";
                                                cout<<seq[0]+1<<endl;
                                                stat = true;
                                                break;
                           }
                  }
                   if(stat)
                           break;
                  }
                  if(!stat)
                           cout<<"no arbitrage sequence exists\n";
    }
    return 0;
}
Contact GitHub API Training Shop Blog About
© 2016 GitHub, Inc. Terms Privacy Security Status Help

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

UVA104번 질문 드립니다.

hijigoo 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말