[원] 동반 예선 A 문제 - 똑똑 한 원숭이 - GCD + DP

제목:
똑똑 한 원숭이 Time Limit: 2000 / 1000 MS (Java / Others) Memory Limit: 32768 / 32768 K (Java / Others) Total Submission (s): 1123 Accepted Submission (s): 294 Problem 숲 속 에 바나나 나무 (무한 길이) 가 줄 지어 있 고 원숭이 한 마리 가 그 중 한 나무 에 서 있다. 원숭이 는 도약 하기 전에 카드 한 장 을 뽑 아야 한다. 카드 에 A + 1 개의 자연수 가 적 혀 있다.그 중 마지막 하 나 는 B 이 고 앞의 A 개 수 는 B 보다 작 을 수 있 으 며 카드 의 숫자 는 같 을 수 있다.원숭이 는 매번 점프 할 때마다 카드 에서 자연수 C 를 선택 한 다음 왼쪽으로, 오른쪽으로 C 그루 의 나 무 를 뛴다.원숭이 의 임 무 는 왼쪽 에 인접 한 바나나 나무 에 뛰 어 올 랐 을 때 위의 바 나 나 를 먹 을 수 있다 는 것 이다.예 를 들 어 A = 2, B = 4 일 때 카드 (2, 3, 4) 에 대해 원숭이 는 바 나 나 를 먹 을 수 있다. 원숭이 는 먼저 왼쪽으로 세 그루 의 나 무 를 뛰 고 오른쪽으로 두 그루 의 나 무 를 뛰 어 넘 을 수 있다.카드 (2, 2, 4) 에 대해 서 는 원숭이 가 왼쪽 에 인접 한 바나나 나무 에 뛰 어 들 수 없다.A 와 B 가 확인 되면 모두 B ^ A 장의 다른 카드 가 있 을 수 있 습 니 다.문 제 는 이 모든 카드 중 원숭이 가 임 무 를 수행 할 수 있 는 카드 가 몇 장 이 냐 는 것 이다.Input 1 줄 k 는 k 조 테스트 데이터 가 있 음 을 나타 내 며, k < = 100 2 ~ k + 1 줄, 각 줄 마다 자연수 A 와 B 를 빈 칸 으로 나 누 어 표시 합 니 다 (A < = 10, B < = 20). Output 총 k 줄, 각 줄 의 숫자 는 각 조 의 데 이 터 를 나타 내 며, 원숭이 를 왼쪽 에 인접 한 바나나 나무의 카드 수로 뛰 어 내 릴 수 있 습 니 다. Sample Input 3 2, 3, 4, 85 13 Sample Output 8 3840 371292
사고: (이 문제 의 데 이 터 는 비교적 작다) B ^ A 카드 에 대해 서 는 카드 에 있 는 모든 숫자 두 칸 의 GCD = = 1 의 경우 에 만 원숭이 에 게 바 나 나 를 먹 일 수 있다. GCD 연산 을 구하 여 교환 율 을 만족 시 키 기 때문에 카드 에 반드시 숫자 B 가 있 기 때문에 하나의 숫자 B 만 있 는 카드 를 초기 상태 로 보고 dp (i, j) 를 사용한다.기록 B 숫자 만 있 는 카드 에 i 숫자 (중복 가능) 를 넣 었 을 때 GCD = j 카드 의 수 입 니 다. s 는 모든 숫자 를 매 거 하고 방정식 을 옮 깁 니 다. dp (i, gcd (s, j)) +=  dp (i - 1, j). 이렇게 하면 앞의 연산 결 과 를 반복 적 으로 이용 할 수 있다.
코드 는 다음 과 같 습 니 다:
 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 30

int dp[maxn][maxn];
int gcd(int a, int b)
{
  while(a)
  {
    int t = a;
    a = b % a;
    b = t;
  }
  return b;
}

void test(int a, int b)
{
  for(int i = 0; i <= a; i++)
  {
    for(int j = 0; j <= b; j++)
      cout<<dp[i][j]<<" ";
    cout<<endl;
  }
}
int main()
{
  int a, b;
  while(scanf("%d%d",&a,&b) != EOF)
  {
    memset(dp, 0, sizeof(dp));
    dp[0][b] = 1;
    for(int i = 1; i <= a; i++)
      for(int j = 1; j <= b; j++)
        if(dp[i-1][j])
          for(int s = 1; s <= b; s++)
            dp[i][gcd(s,j)] += dp[i-1][j];
    //test(a,b);
    cout<<dp[a][1]<<endl;
  }
}

이 문 제 는 poj 1091 의 개편 으로 데 이 터 를 줄 였 다.
저자: u011652573 발표 2014 - 4 - 11 13: 08: 23
링크
평론
댓 글 보기