[HDU 2451]Simple Addition Expression(조합 수학 또는 디지털 DPSimple Addition Expression)

Simple Addition Expression
제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=2451
제목 의 대의:
연속 적 인 세 개의 수의 합 을 계산 하 는 계산기 가 있 지만 이 계산 기 는 비교적 낮 아서 들 어 갈 수 없다.예 를 들 어 0+1+2,계산 기 는 3 을 계산 하지만 3+4+5 계산 기 는 2 만 계산 할 수 있다.정 답 은 12 입 니 다.들 어 갈 수 없 기 때 문 입 니 다.1 을 그냥 버 렸 어 요.
지금 은 N 을 세 어 주 겠 습 니 다.[0,N)의 범위 내 에 몇 개의 숫자 가 있 는 지 계산 기 는 정 답 을 계산 할 수 있 도록 합 니 다.
문제 풀이 방향:
제 생각 은 이 렇 습 니 다.수학 주 제 를 조합 하 는 문제 이기 때문에 저 는 이 방면 에 기대 고 싶 습 니 다.그리고 자신의 자세 가 항상 아름 답지 않다 는 것 을 알 게 되 었 다)
　　
먼저 한 자릿수 를 분석 하면 이 수 는 0,1,2 에 불과 하 다. 
그 다음으로 두 자릿수 를 분석 하면 한 자릿수 가 같 고 열 자릿수 는 1,2,3 이 될 수 있다.
이 어 세 자릿수 를 분석 하면 한 자릿수 가 같 고 열 자릿수 는 0,1,2,3 이 될 수 있다.백 자리 수 는 1,2,3.
그래서 한 N 자리수 에 대해 최고 위 는 3 가지 선택 이 있 고 한 자 리 는 3 가지 선택 이 있 으 며 나머지 는 4 가지 선택 이 있다 는 것 을 어렵 지 않 게 알 수 있다.즉 3*4*...*4*3(N>=3)
그리고 나 서 나 는 바로 이 숫자 가 몇 자리 인지 보 았 다.N 자리 라면 1 자리 부터 N-1 자리 까지 모두 계산 하기 쉽다.다음은 N 자리수 입 니 다.N 자리수 판단 은 번 거 롭 습 니 다.가장 높 은 자리 에서 하나씩 밀어 야 합 니 다.만약 에 가장 높 은 자리 가 3 보다 작 으 면 k 입 니 다.그러면 가장 높 은 자리 에서 1 에서 k-1 을 취 할 때 뒤의 자릿수 는 같 지만 가장 높 은 자리 에서 k 를 취 했 을 때 다음 의 수 치 를 고려 해 야 한다.이런 식 으로 미 루 는 것 은 매우 번 거 로 웠 다.그리고 나 는 포기 했다.왜냐하면 이렇게 하 는 것 보다 디지털 DP 로 하 는 것 이 낫 다 는 것 을 알 았 기 때문이다.
디지털 DP 의 해법.구체 적 인 방법 은 코드 를 보십시오.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 1000
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;
int pos, bit[12];
void open(ll n)
{
    pos = -1;
    while(n)
    {
        bit[++pos] = n % 10;
        n /= 10;
    }
}
int f[12][4];
ll dfs(int pos, int s, bool e)
{
    if (pos == -1) return (s != 3); //        ，      ，   3    。 s == 3    ，return 0
    if (!e && f[pos][s] != -1) return f[pos][s];
    ll res = 0;
    int u = e ? bit[pos] : 3;
    if (u > 3) u = 3; //       ，wa 。      ，u    bit[pos]  ，     3，            3   。             
    for (int d = 0; d <= u; d++)
    {
        res += dfs(pos - 1, d, e && d == bit[pos]);
    }
    return e ? res : f[pos][s] = res;
}
void solve(ll n)
{
    mem(f, -1);
    cout<<dfs(pos, 0, 1)<<endl;
}
int main ()
{
    ll n;
    while(~scanf("%I64d", &n))
    {
        n--;
        open(n);
        solve(n);
    }
    return 0;
}

나중에 다른 사람의 문제 보고 서 를 보고 자신 이 약 해 졌 다 는 것 을 알 게 되 었 다.
사실 나 는 숫자 를 1 에서 N 자리 로 나 누 어 할 필요 가 전혀 없다.직접 N 자리 로 고려 해 보 자.앞 에 0 이 있 으 면 숫자 가 줄 어 든 것 이 잖 아.

int main ()
{
    ll n;
    while(cin>>n)   //hdu  long long      %lld  。。    （      ）
    {
        open(n);
        ll ans = 0;
        bool flag = false;
        for (int i = pos; i >= 1; i--)
        {
            if (bit[i] > 3) flag = true;
            if (flag) //         3，        
            {
                ans += 3 * pow(4.0, i); //                ，      ，      0,1,2,3     。
                break;
            }
            ans += bit[i] * 3 * pow(4.0, i - 1); // bit[i]    3   ，     0,1,……bit[i]。
        }
        if (!flag) ans += (bit[0] > 3 ? 3 : bit[0]); //      ，  flag false，         bit[i]  3，       
        cout<<ans<<endl;
    }
    return 0;
}