[2017 바이두의 별 프로그램 설계 대회 - 재경기] E - hdu6148
직접 틀에 오르다.
#include
#include
#include
#include
#define ll long long
using namespace std;
const int N=110,P=1000000007;
ll f[N][2][10],a[N],n;
ll dfs(ll pos,ll st,ll lim,ll pre)
{
if(pos==-1) {if(~pre)return 1;else return 0;}
if(!lim&&~pre&&~f[pos][st][pre])return f[pos][st][pre];
ll up=lim?a[pos]:9;ll ans=0;
for(int i=0;i<=up;i++)
{
if(pre==-1&&i==0)ans=(ans+dfs(pos-1,st,lim&&i==up,pre))%P;else
if(pre==-1&&i!=0)ans=(ans+dfs(pos-1,st,lim&&i==up,i))%P;else
if(st==0)ans=(ans+dfs(pos-1,i>pre,lim&&i==up,i))%P;else
if(st==1&&i>=pre)ans=(ans+dfs(pos-1,st,lim&&i==up,i))%P;
}
if (!lim&&~pre) f[pos][st][pre]=ans;
return ans;
}
char s[N];ll T;
int main()
{
register int i,j,l;
scanf("%lld",&T);
memset(f,-1,sizeof(f));
for (l=1;l<=T;l++)
{
scanf("%s",s+1);
n=strlen(s+1);
for(i=1;i<=n;i++) a[n-i]=s[i]-'0';
printf("%lld
",dfs(n-1,0,1,-1));
}
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
zoj3966 Domino Tiling dp제목 대의: n*m의 바둑판을 주면 1x2의 칸으로만 조립할 수 있고 4개의 다른 칸의 뿔이 동시에 한 곳에 모일 수 없다.200조 정도의 입력과 출력 임의의 방안. 문제풀이: 제한 조건이 너무 강하기 때문에 가장 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
