HDU 2089 싫어 62(디지털 DP)
6068 단어 디지털 dp
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<vector>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define maxn 1005
#define f(x) (x*1.0)
#define inf 0x3f3f3f3f
#define maxm maxn*maxn
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)
#define lowbit(x) (x&(-x))
#define cheak(i) printf("%d ",i)
#define lson(x) (splay[x].son[0])
#define rson(x) (splay[x].son[1])
#define rfor(i,a,b) for(i=a;i<=b;++i)
#define lfor(i,a,b) for(i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define mec(a,b) memcpy(a,b,sizeof(b))
//0
//1 2
//2
int dp[25][3];
void init()
{
dp[0][0]=1;
dp[0][1]=dp[0][2]=0;
int i;
rfor(i,1,20)
{
dp[i][0]=dp[i-1][0]*9-dp[i-1][1];
dp[i][1]=dp[i-1][0];
dp[i][2]=dp[i-1][2]*10+dp[i-1][0]+dp[i-1][1];
}
}
int A[25];
int solve(int x)
{
int len=0,ans=0,i;
while(x)
{
A[++len]=x%10;
x/=10;
}
A[len+1]=0;
bool flag=false;
lfor(i,len,1)
{
ans+=dp[i-1][2]*A[i];
if(flag) ans+=dp[i-1][0]*A[i];
else
{
if(A[i]>4) ans+=dp[i-1][0];
if(A[i]>6) ans+=dp[i-1][1];
if(A[i+1]==6&&A[i]>2) ans+=dp[i][1];
}
if(A[i]==4||A[i]==2&&A[i+1]==6) flag=true;
}
if(flag) ans++;
return ans;
}
int main()
{
int l,r;
init();
while(~scanf("%d%d",&l,&r))
{
if(!l&&!r) break;
l--;
int ans=r-l;
l=solve(l);
r=solve(r);
ans-=r-l;
printf("%d
",ans);
}
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에 따라 라이센스가 부여됩니다.