hdu4734(디지털 DP)
1186 단어 DP
f(0)~f(B) 중 f(A)보다 작은 것이 몇 개 있는지 구하기;
함수 f는 한 숫자의 한 자리를 나누고 오른쪽에서 첫 번째 *2^0+두 번째 *2^1...n위*2^(n-1);
아이디어:
디지털 DP;
dp[i][j]는 i위가 j보다 작은 수가 몇 개라는 것을 나타낸다.
#include
#include
int A,B,dp[11][50000],a[25];
int len;
int f(int n){
int ans = 0,len = 1;
while(n){
ans += n % 10 * len;
len *= 2;
n /= 10;
}
return ans;
}
int dfs(int len,int ans,int flag){
if(len < 0)
return ans >= 0;
if(ans < 0)
return 0;
int sum = 0;
if(!flag && dp[len][ans] != -1)
return dp[len][ans];
int m = flag ? a[len] : 9;
for(int i = 0; i <= m; i++) {
sum += dfs(len - 1, ans - i * (1 << len), flag && i == m);
}
if(!flag)
dp[len][ans] = sum;
return sum;
}
int main(){
int t,cas = 1;
scanf("%d",&t);
memset(dp,-1,sizeof(dp));
while(t--){
scanf("%d%d",&A,&B);
len=0;
while(B){
a[len++] = B % 10;
B /= 10;
}
printf("Case #%d: %d
",cas++ ,dfs(len - 1,f(A) , 1));
}
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
