디지털 dp는 일종의 계수용 dp로 일반적으로 하나의 구간 [le,ri]에서 일부 조건수를 만족시키는 개수를 통계해야 한다.이른바 디지털 dp란 글자의 뜻은 바로 디지털 위에서 dp를 진행하는 것이다.수위는 그래도 비교적 듣기 좋은 이름이다. 수위의 의미는 한 수에 한 자리, 열 자리, 백 자리, 천 자리가 있다.한 명씩 세면 숫자야!
디지털 개념을 도입하는 것은 완전히 dp를 위한 것이다.디지털 dp의 실질은 폭력적인 매거 방식을 바꾸어 새로운 매거 방식이 dp의 성질을 만족시키고 기억화하면 된다는 것이다. 두 가지 다른 매거: 하나의 구간[le,ri]이 조건수를 만족시키는 개수에 대해 가장 간단한 폭력은 다음과 같다.
[cpp] view plain copy
for(int i=le;i<=ri;i++)
if(right(i)) ans++;
그러나 이런 매거는 기억화하기 불편하거나 전혀 컨디션이 없다.
새로운 매거진: 상계 매거진을 제어하고 가장 높은 위치부터 아래로 매거진한다. 예를 들어 리=213이다. 그러면 우리는 백 위치부터 매거진한다. 백 위치가 가능한 상황은 0,1,2이다. (여기에 0을 매거하는 것이 문제가 있다고 생각하는 사람은 계속한다) 그리고 한 명의 매거는 매거진의 이 수를 상계 213(하계는 0 또는 1, 이 부차적인 것)을 초과할 수 없다. 백 명이 1을 매거하면 열 명의 매거는 0에서 9이다. 백 명의 1은 상계 2보다 작기 때문에 뒤에 있는 매거는 아무것도 상계를 초과할 수 없다.그래서 문제는 고위 매거가 상계에 딱 도달하면 그 다음에 이어지는 매거에 상계 제한이 있다는 점이다.구체적으로 여기서 만약에 백 명이 2를 매거했다면 열 명의 매거 상황은 0에서 1이다. 만약에 앞의 두 명이 21을 매거했다면 마지막 한 명이 0에서 3이다.마지막 문제: 최고위 매거 0: 백위 매거 0은 이때 내가 매거한 이 수가 가장 많은 두 자릿수에 해당한다. 만약에 10명이 계속 0을 매거한다면 내가 매거한 것은 바로 숫자인 줄 알았다. 왜냐하면 우리가 매거하는 것은 리와 같은 숫자보다 작기 때문에 숫자가 적으면 안 된다. 당연히 리보다 작은 숫자를 매거할 수 없다!(이렇게 매거는 누락되지 않은 매거를 위한 것이다. 그러나 하나의 문제를 가져올 수 있다. 바로 전도 0의 문제이다. 템플릿에 lead 변수로 표시하지만 이것은 모든 문제가 영향을 미치는 것이 아니다. 전도 0이 우리의 계수에 영향을 주지 않을 수도 있다. 구체적으로 문제를 보아야 한다) 이러한 새로운 열거는 상계만 제어하기 때문에 우리의 Main 함수는 항상 이렇다.
[cpp] view plain copy
int main()
{
long long le,ri;
while(~scanf("%lld%lld",&le,&ri))
printf("%lld",solve(ri)-solve(le-1));
}
w_w 그렇죠![1,ri] 수량과 [1,le-1]을 통계한 다음에 상감하면 구간 [le,ri]의 수량이다. 여기서 내가 쓴 하계는 1이고 사실 0도 된다. 어차피 상감하면 없어진다. 제목에서 l의 범위는 모두 1보다 크다는 것을 주의한다(그렇지 않으면le=0, 하나 더 줄이면 G G)
예제를 말하기 전에 기본적인 동적 템플릿을 말하라(뒤의 예제를 먼저 보아도 된다): dp사상은 현재 위치pos까지 매거하고 상태는state(이것은 제목에 근거한 것이기 때문에 많을 수 있다. dp는 천변만화된다)의 수량(계수인 이상 dp값은 조건을 충족시키는 개수임이 분명하다)
[cpp] view plain copy
typedef long long ll;
int a[20];
ll dp[20][state];//제목마다 상태가 다르다
lldfs(int pos,/*state 변수*/,bool lead/* 리드 제로*/,bool limit/* 수위 상계 변수*/)//모든 문제에서 리드 제로를 판단해야 하는 것은 아니다
{
//귀속 경계, 기왕 위치별로 매거한 이상 최저 위치는 0,pos=-1은 이 수를 내가 매거했다는 것을 설명한다
if(pos==-1) return 1;/*여기서 일반적으로 1을 되돌려주는 것은 당신이 매거한 이 수가 합법적이라는 것을 의미한다. 그러면 여기서 매거할 때 반드시 모든 사람이 제목의 조건을 만족시켜야 한다. 즉, 현재 매거한pos위까지 매거하고 앞에서 이미 매거한 수가 합법적이라는 것을 반드시 보증해야 한다.그러나 구체적인 제목이 다르거나 쓰기 방법이 다르면 반드시 1*/
/* 일반적인 문법은 모두 제한이 없는 조건에서 기억화되는데 여기에 아래의 기록 상태와 대응한다. 구체적으로 왜 조건이 있는 기억화인지 뒤에 */
를 말한다.
int up=limit?a[pos]:9;//limit의 판단에 따라 매거된 상계 up;이 예는 앞에서 213으로 말했다
ll ans=0;
//시작 계수
for(int i=0;i<=up;i++)//매거진 후 서로 다른 상황의 개수를ans에 추가하면 됩니다
{
if() ...
else if()...
ans+=dfs(pos-1,/*상태이동*/,lead&&&i==0,limit &&&&&i=a[pos])//마지막 두 변수 전참은 모두 이렇게 썼다
/*여기는 비교적 유연한 편이지만 몇 문제를 풀면 여기도 방법이 있다고 생각한다
대략적으로 말하면 현재 나의 디지털 매거 수는 i이고 제목의 구속 조건에 따라 분류하여 토론한다
서로 다른 상황에서의 개수를 계산하고state 변수에 따라 i의 합법성을 확보해야 한다. 예를 들어 제목
디지털에 62가 연속적으로 나타나지 않도록 요구한다. 그러면state는 전위pre를 저장하고 분류하는 것이다
전위가 6이라면 2가 될 수 없다. 여기에 반드시 매거한 이 수를 보존해야 하는 것은 합법적이다*/
}
//계산 완료, 상태 기록
if(!limit && !lead) dp[pos][state]=ans;
/*여기에는 위의 기억화에 대응하고 일정한 조건하에서 기록할 때 일치성을 확보한다. 물론 제약 조건이 lead를 고려할 필요가 없다면 여기가 바로 lead이다. */
return ans;
}
ll solve(ll x)
{
int pos=0;
while(x)//숫자를 모두 분해
{
a[pos++]=x%10;//개인은 항상 [0,pos) 번호를 좋아하고 익숙하지 않은 것은 자신의 습관대로 한다. 어쨌든 디지털 경계에 주의하면 된다
x/=10;
}
return dfs(pos-1/*최고위부터 매거*/,/* 일련의 상태*/,true,true);//처음에는 최고위도 제한이 있고 선도 제로가 있는데, 분명히 최고위보다 높은 사람은 0으로 간주하잖아
}
int main()
{
ll le,ri;
while(~scanf("%lld%lld",&le,&ri))
{
//dp수 그룹을 -1로 초기화하면 여기에 더욱 아름다운 최적화가 있다. 뒤에 말하자면
printf("%lld",solve(ri)-solve(le-1));
}
}
예제 [HDU2089] 아니 6, 2. 중국어 의 주제면 은 제목 의 뜻 이 매우 이해하기 쉬우므로, 여기 는 더 이상 군말 하지 않겠다 이것은 디지털 DP의 입문 문제입니다. 디지털 DP의 원리와 기본 구조를 잘 이해할 수 있습니다. 위의 템플릿은 매우 상세하고 일반적인 디지털 DP 문제를 해결할 수 있습니다. 이 문제는 매우 간단합니다. 바로 코드를 올립니다.
【HDU6148】Valley Number 이것 도 중국어 문제 인데, 제목 의 뜻 을 잘 알면 바로 숫자 를 왼쪽 에서 오른쪽 으로 보면 먼저 점차 증가한 뒤 점차 줄어드는 상황 이 없도록 하면 된다 이 문제는 위의 템플릿만 수정하면 됩니다. 디지털 DP 문제의 관건은 다음 숫자의 상황을 어떻게 분석하는가입니다.
ll dfs(int pos, int pre, int turn, bool limit, bool invalid)
// pos DP ，pre,turn,limit,invalid... ，
// ， dfs
//
마찬가지로 코드를 직접 보아라. 이런 문제의 관건은 네가 어떻게 모든 숫자를 확정하는 과정을 이해하는 데 있다
