UVA 10795 A Different Task(반복 상태 전환)

2854 단어 uva10795
해석은 류여가의 《알고리즘 경기 입문 클래식 트레이닝 가이드》 P27을 보십시오
#include <cstdio>
#include <cstring>
typedef long long ll;
const int N = 65;
int n, start[N], finish[N];
ll f(int p[],int i,int fin) {
    if(i == 0)
        return 0;
    if(p[i] == fin)
        return f(p,i-1,fin);
    return f(p,i-1,6-p[i]-fin) + (1LL << (i-1));
} 
int main() {
    int cas = 1;
    while(scanf("%d",&n) != EOF && n) {
        for(int i = 1; i <= n; i++) {
            scanf("%d",&start[i]);
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d",&finish[i]);
        }
        int k = n;
        while(k >= 0 && finish[k] == start[k]) {
            k--;
        }
        ll ans = 0;
        if(k >= 1) {
            int other = 6 - start[k] - finish[k];
            ans = f(start,k-1,other) + f(finish,k-1,other) + 1;
        }
        printf("Case %d: %lld
"
,cas++,ans); } return 0; }

좋은 웹페이지 즐겨찾기