POJ 3634 circle of debt

POJ-3634
제목: 세 사람 이 있 습 니 다. a 는 b, b 는 c, c 는 a 에 게 빚 을 졌 습 니 다. 그리고 그들 은 자신 에 게 돈 이 있 습 니 다. 1, 5, 10 에서 100, 몇 개 (몇 개 있 는 지 알려 드 리 겠 습 니 다).최소 몇 번 교환 하면 빚 을 갚 을 수 있 냐 고 물 었 다.
문제 풀이:
결국 서로 빚 진 만큼 갚 을 필요 가 없다.
해결 방향:
우선 모든 사람 에 게 dfs 를 처리 하고 얼 마 를 찾 았 는 지 갚 습 니 다.생각 하지 않 아 도 터 질 거 야.
최 적 화 를 고려 하 다.
본질 최적화: 동전 의 종류 에서 검색 합 니 다.동전 마다 누가 썼 는 지 생각해 보 세 요.
최적화 1:
가설: 3 이 점 을 고려한다.
1 은 2a 원, 2 는 3b 원 을 주 었 습 니 다.
a
a > b: 1 은 2 a - b 원, 1 은 3 b 원 을 준 셈 이다.
b 에서 의 전환 을 줄 이 고 처리 하기 편리 한 동시에 1 과 3 간 의 관계 도 동시에 처리 했다.
최적화 2:
가장 좋 은 가지치기: 현재 가장 좋 은 답 보다 큰 것 은 직접 return 할 수 있 습 니 다.더하기 없 이 너 도 T (QAQ)
타당 성 가지치기: 최종 상태 에 도달 하기 위해 부채 차액 의 보완 = x * 100 + y * 50 +.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define LL long long
using namespace std;
/*      */

const int inf   = 1000000000;
int mon[7]={0,100,50,20,10,5,1};
int M[10][10],debt[10],ans,cnt;

bool check(int x,int money)
{
    switch(x)
    {
        case 1:return money % 100 == 0;
        case 2:return money % 50 == 0;
        case 3:case 4:return money % 10 == 0;
        case 5:return money % 5 == 0;
        case 6:return true;
    }
}

void dfs(int x)
{
    if(x==0){if(debt[1]==debt[2]&&debt[2]==debt[3])ans=min(ans,cnt);return;}
    if(cnt>=ans)return;
    if(!check(x,debt[1]-debt[2])||!check(x,debt[2]-debt[3]))return;
    //cout<>T;
    while(T--)
    {
        init();
    }
    system("pause");
}

POJ 3634 circle of debt

좋은 웹페이지 즐겨찾기