hdu 4722 Good Numbers(초 섭 디지털 dp)
1955 단어 디지털 dp
대체로 한 정수 에 있 는 여러분 의 숫자 가 10 의 배수 라면 이 수 를'good number'라 고 부 릅 니 다.구간[A,B]을 제시 하고 이 구간 내'good number'의 수의 개 수 를 구하 세 요.
첫 번 째 디지털 dp 는 한참 을 뒤 척 이 고 나 서 야 어떻게 된 일 인지 알 게 되 었 다.
dp[site][mod]를 설정 하여 사이트 위치(높 은 위치 에서 낮은 위치 로)앞 에 있 는 숫자 와 10 에서 mod 로 남 은 수의 개 수 를 기억 화 검색 합 니 다.두 가지 중요 한 점 이 있 습 니 다.먼저 변수 up 은 경계 에 도 착 했 는 지 여 부 를 표시 합 니 다.up 은 0 은 도착 하지 않 았 음 을 표시 합 니 다.up 은 1 은 경계 에 도 착 했 음 을 표시 합 니 다.up 의 수치 가 뒷 자리 수의 수치 범 위 를 결정 합 니 다.0-9 인지 0-dig[site]인지 결정 합 니 다.그 다음 에 기억 화 된 조건 입 니 다.dp[site][mod]는 경계 에 도달 하지 못 한 상황 을 기록 하고 공용 결과 에 해당 합 니 다.이것 도 기억 화 된 본질 이 고 경계 에 도달 한 것 에 대해 기억 화 할 필요 가 없습니다.
#include <stdio.h>
#include <iostream>
#include <map>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL long long
#define _LL __int64
#define eps 1e-8
#define PI acos(-1.0)
using namespace std;
_LL dp[25][12];
int dig[25];
_LL dfs(int site, int mod, int up)
{
if(site == 0)
return mod == 0 ? 1 : 0; // 。
if(!up && dp[site][mod] != -1) // ，up = 0 dp[site][mod] != -1
return dp[site][mod];
int len = up ? dig[site] : 9; // site
_LL ans = 0;
for(int i = 0; i <= len; i++)
{
ans += dfs(site-1, (mod+i)%10, up && (i == len) );
}
if(!up)
dp[site][mod] = ans;
return ans;
}
_LL cal(_LL x)
{
int cnt = 0;
_LL tmp = x;
if(x < 0)
return 0;
while(tmp)
{
dig[++cnt] = tmp % 10;
tmp /= 10;
}
memset(dp,-1,sizeof(dp));
return dfs(cnt,0,1);
}
int main()
{
int test;
_LL x,y;
scanf("%d",&test);
for(int item = 1; item <= test; item++)
{
cin >> x >> y;
memset(dp,-1,sizeof(dp));
printf("Case #%d: %I64d
",item,cal(y) - cal(x-1));
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Gym 100623J Just To Lucky(디지털 dp)제목: 1-n 중 몇 개의 숫자가 그 자체를 만족시키고 각 수위에 의해 정제될 수 있는지; 사고방식: n은 10의 12차원이다. 곧 디지털 dp라고 생각할 수 있다. 그때는 판자가 없어서 디지털 dp를 어떻게 두드렸...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
