hdu2089 (디지털 dp)
해법: 디지털 dp.
int dfs(int pos,int pre,bool limit,bool have).pos는 dp에서 오는 디지털 위치를 나타내고pre는 앞의 디지털 위치를 나타낸다.limit은 이 시간수가 떨어졌는지(이 위치의 숫자가 제한되었는지의 의미), have는 이전에 62가 있었는지 여부를 나타낸다.4의 배제는 매번 다음 i를 열거할 때마다 4를 얻지 않으면 된다.모든 케이스의 dp값은 같기 때문에 한 번만 계산해야 한다.
코드:
/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>
//freopen ("in.txt" , "r" , stdin);
using namespace std;
#define eps 1e-8
const double pi=acos(-1.0);
typedef long long LL;
const int Max=10100;
const int INF=1000000007;
int dp[15][12];
int num[20];
int p=0;
int dfs(int pos,int pre,bool limit,bool have)
{
if(pos==0)
return !have;
if(have)
return 0;
if(!limit&&dp[pos][pre]!=-1)
return dp[pos][pre];
int en=limit?num[pos-1]:9;
int ans=0;
for(int i=0; i<=en; i++)
{
if(i==4)continue;
ans+=dfs(pos-1,i,limit&&i==en,(pre==6&&i==2));
}
if(!limit)
return dp[pos][pre]=ans;
else
return ans;
}
int getans(int t)
{
if(t==0)
return 0;
p=0;
while(t)
{
num[p++]=t%10;
t/=10;
}
int ans=0;
for(int i=0; i<=num[p-1]; i++)
{
if(i==4)
continue;
ans+=dfs(p-1,i,i==num[p-1],0);
}
return ans-1;
}
int main()
{
int l,r;
memset(dp,-1,sizeof dp);
while(scanf("%d%d",&l,&r)==2)
{
if(r==0&&l==0)
break;
cout<<getans(r)-getans(l-1)<<'
';
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.