[디지털 dp] hdu3709
Balanced Number
Problem Description
A balanced number is a non-negative integer that can be balanced if a pivot is placed at some digit. More specifically, imagine each digit as a box with weight indicated by the digit. When a pivot is placed at some digit of the number, the distance from a digit to the pivot is the offset between it and the pivot. Then the torques of left part and right part can be calculated. It is balanced if they are the same. A balanced number must be balanced with the pivot at some of its digits. For example, 4139 is a balanced number with pivot fixed at 3. The torqueses are 4*2 + 1*1 = 9 and 9*1 = 9, for left part and right part, respectively. It's your job
to calculate the number of balanced numbers in a given range [x, y].
Input
The input contains multiple test cases. The first line is the total number of cases T (0 < T ≤ 30). For each case, there are two integers separated by a space in a line, x and y. (0 ≤ x ≤ y ≤ 10
18).
Output
For each case, print the number of balanced numbers in the range [x, y] in a line.
Sample Input
2
0 9
7604 24324
Sample Output
10
897
한 수가'균형적'인지 아닌지를 판단하다
매거 지점, 산력 모멘트...모멘트가 마이너스일 때 직접 가지를 잘라도 되는데...#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long a, b;
long long f[30][30][2005];
int bit[30];
long long dp(int pos, int x, int st, int flag) //st
{
if (pos == 0) return st == 0;
if (st < 0) return 0;
if (flag && f[pos][x][st] != -1) return f[pos][x][st];
int d = flag ? 9 : bit[pos];
long long ans = 0;
for (int i = 0; i <= d; i++)
{
int tmp = st + i * (pos - x);
ans += dp(pos - 1, x, tmp, flag || i != d);
}
if (flag) f[pos][x][st] = ans;
return ans;
}
long long solve(long long n)
{
if (n < 0) return 0;
int len = 0;
while (n > 0)
{
bit[++len] = n % 10;
n /= 10;
}
long long res = 0;
for (int i = 1; i <= len; i++)
{
res += dp(len, i, 0, 0);
}
return res - len + 1;
}
int main()
{
int t;
scanf("%d", &t);
memset(f, -1, sizeof(f));
while (t--)
{
cin >> a >> b;
cout << solve(b) - solve(a - 1) << endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)
의 해설 기사입니다.
해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다.
※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다.
문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
2
0 9
7604 24324
10
897
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long a, b;
long long f[30][30][2005];
int bit[30];
long long dp(int pos, int x, int st, int flag) //st
{
if (pos == 0) return st == 0;
if (st < 0) return 0;
if (flag && f[pos][x][st] != -1) return f[pos][x][st];
int d = flag ? 9 : bit[pos];
long long ans = 0;
for (int i = 0; i <= d; i++)
{
int tmp = st + i * (pos - x);
ans += dp(pos - 1, x, tmp, flag || i != d);
}
if (flag) f[pos][x][st] = ans;
return ans;
}
long long solve(long long n)
{
if (n < 0) return 0;
int len = 0;
while (n > 0)
{
bit[++len] = n % 10;
n /= 10;
}
long long res = 0;
for (int i = 1; i <= len; i++)
{
res += dp(len, i, 0, 0);
}
return res - len + 1;
}
int main()
{
int t;
scanf("%d", &t);
memset(f, -1, sizeof(f));
while (t--)
{
cin >> a >> b;
cout << solve(b) - solve(a - 1) << endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.