POJ 3286
2464 단어 poj
수학: 30줄 코드, 94MS;
DP: 69줄 코드, 63MS,
수학 반복 cpp:
#include<cstring>
#include<cstdio>
using namespace std;
void cac(long long con,long long &cnt,long long t)
{
if(con<=0)
return;
long long x,y,n=con/10;
long long i,j;
x=con/10,y=con%10;
for(;x!=0;x/=10)
if(x%10==0)
cnt+=(y+1)*t;
cnt+=n*t;
cac(n-1,cnt,t*10);
}
int main()
{
long long m,n;
while(scanf("%lld%lld",&m,&n),m>=0)
{
long long sum1=0,sum2=0;
cac(m-1,sum1,1ll);
cac(n,sum2,1ll);
if(m==0)
sum2++;
printf("%lld
",sum2-sum1);
}
return 0;
}
DP:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long dp[2][15][15];
long long ten[15];
long long dfs(long long n)
{
if(n<0)
return 0;
else if(n==0)
return 1;
long long a[15],len,nn=n;
for(len=0;n;len++)
{
a[len]=n%10ll;
n/=10ll;
}
reverse(a,a+len);
long long ans=0,tp=a[0]-1ll;
if(tp!=0)
for(long long i=1;i<=len-1;i++)
ans+=tp*dp[0][len-1][i]*i;
for(long long i=1;i<=len-1;i++)
for(long long j=1;j<i;j++)
ans+=dp[1][i][j]*j;
for(long long i=1;i<len;i++)
{
tp=a[i]-1ll;
if(tp>0ll)
{
for(long long j=1;j<=len-i-1;j++)
ans+=tp*dp[0][len-i-1][j]*j;
}
if(tp!=-1ll)
{
for(long long j=0;j<=len-i-1;j++)
ans+=dp[0][len-i-1][j]*(j+1ll);
}
else
ans+=nn%ten[len-i-1]+1ll;
}
return ans+1ll;
}
int main()
{
memset(dp,0,sizeof(dp));
dp[0][0][0]=1;
dp[0][1][1]=1;
dp[0][1][0]=9;
dp[1][1][0]=9;
ten[0]=1;
for(long long i=1;i<=13;i++)
ten[i]=ten[i-1]*10;
for(long long i=2;i<=13;i++)
{
for(long long j=0;j<i;j++)
dp[1][i][j]=dp[0][i-1][j]*9;
dp[0][i][0]=9*dp[0][i-1][0];
for(long long j=1;j<=i;j++)
dp[0][i][j]=dp[0][i-1][j-1]+9*dp[0][i-1][j];
}
long long n,m;
while(scanf("%lld%lld",&m,&n)&&m>=0)
{
printf("%lld
",dfs(n)-dfs(m-1));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.