poj 1790 Base Numbers(dp)
1782 단어 Numbers
[문제풀이 사고방식]: 어떤 진수에서 i위까지 숫자를 나타내는 개수...dp[i]=sigema(dp[j])(j>=0 & & j조건은 두 가지가 있다. 첫째, 그것의 앞부분의 숫자는 반드시 진수보다 작아야 한다. 둘째, 그것이 하나의 숫자가 아니면 첫 번째 숫자는 0이 될 수 없다.(와라.. 여기)
큰 환경 1개: 진법의 수위는 0이 될 수 없다.
【코드】:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#include <cctype>
#include <map>
#include <iomanip>
using namespace std;
#define eps 1e-8
#define pi acos(-1.0)
#define inf 1<<30
#define linf 1LL<<60
#define pb push_back
#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
#define lowbit(x) (x & (-x))
#define ll long long
int len;
char s[50];
int cnt[50];
int cnt_num(int r){
int n;
n=len;
if (s[n-r]=='0') return 0;
cnt[0]=1;
for (int i=1; i<=n-r; i++){
cnt[i]=0;
int minn;
if (i-r<0) minn=0;
else minn=i-r;
for (int j=minn; j<i; j++){
if ((j+1<i || j==0 && n-r>1) && s[j]=='0') continue;
if (j+r==i) if (strncmp(s+j,s+n-r,r)>=0) continue;
cnt[i]+=cnt[j];
}
}
return cnt[n-r];
}
int main(){
int r,c;
while (1){
scanf("%s",s);
if (s[0]=='#') break;
len=strlen(s);
int ans=0;
for (int i=1; i<len; i++)
ans+=cnt_num(i);
if (ans>0)
printf ("The code %s can represent %d numbers.
",s,ans);
else printf ("The code %s is invalid.
",s);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Fibonacci with ADA and others (Part 2/3)The current source code implements the second approach, where it declares that maximum value for each component as a con...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.