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; }

좋은 웹페이지 즐겨찾기