HDU 2089 디지털 DP
사고방식: dp[i][0]: 상위 i위 1위가 4라는 불길한 개수를 나타낸다
pp[i][1]: 전 i위 i+1위가 6의 불길한 개수임을 나타낸다.
dp[i][2]: 앞의 i위가 불길한 수를 포함하고 있음을 나타낸다
eg:
n=100,a[1]=0,a[2]=0,a[3]=1;
dp[1][0] = 1은 4이다.
dp[1][1]=2 62,64;
dp[1][2]= 10 40,41,42,43,44,45,46,47,48,49;
dp[2][0]=20 = dp[1][0]+dp[1][1]+dp[1][2]+14,24,34,54,74,84,94;
#include<stdio.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<iostream>
using namespace std;
int a[20];
int dp[20][3];
int dfs(int pos, int st, bool flag)
{
if(pos == 0)
return st == 2;
if(flag && dp[pos][st] != -1)
return dp[pos][st];
int ans = 0;
int u = flag ? 9 : a[pos];
for(int i = 0; i <= u; i++)
{
if(st == 2 || i == 4 || (st == 1 && i == 2))
ans += dfs(pos-1, 2, flag || i < u);
else if(i == 6)
ans += dfs(pos-1, 1, flag || i < u);
else ans += dfs(pos-1, 0,flag || i < u);
}
if(flag) dp[pos][st] = ans;
return ans;
}
int cal(int n)
{
int len = 0;
while(n)
{
a[++len] = n % 10;
n /= 10;
}
return dfs(len, 0, 0);
}
int main()
{
int n,m;
memset(dp, -1, sizeof(dp));
while(~scanf("%d%d",&n, &m))
{
if(n == 0 && m == 0)
return 0;
printf("%d
",m - n + 1 - cal(m) + cal(n-1));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
