디지털 DP - 숫자 1 수
1783 단어 동적 기획
기준 시간 제한: 1초 공간 제한: 131072KB점수: 5난이도: 1급 알고리즘 문제
1부터 N까지의 모든 양의 숫자를 적은 십진수 N을 지정하여 1의 개수를 계산합니다.
예를 들어 n = 12 에는 1 이 5 개 들어 있습니다.1,10,12에는 3개의 1,11에는 2개의 1,총 5개의 1이 포함된다.
Input
N(1 <= N <= 10^9)
Output
1
Input 예
12
Output 예
5
dp[i]는 1~10^(i-1)내 숫자 1의 개수를 나타낸다
for(int i=1;i<15;++i)
{
dp[i]=dp[i-1]*10+po;
po*=10;
}
그리고 모든 숫자에 대해 숫자와 1의 관계를 고려해야 한다.예를 들어 141과 같이 세 번째 1이 되었을 때 사실상 1~41의 1의 수량을 계산해 냈다. 그러면 나는 이 수량을 100~141에서 시작의 1의 수량을 제외하고 42개의 시작의 1을 더하면 이것은 아직 계산하지 않았다고 생각했다.그리고 또 하나는 1~99의 1의 수량이다.
if(digit>1) ans+=digit*dp[i-1]+po;
else if(digit==1) ans+=dp[i-1]+tail+1;
여기의ans는 끊임없이 누적되어 각 위의 1의 숫자를 표시해야 한다.code:
#include
#include
#include
#define LL long long
using namespace std;
LL dp[15];
void init()
{
memset(dp,0,sizeof(dp));
LL po=1;
for(int i=1; i<15; ++i)
{
dp[i]=dp[i-1]*10+po;
po*=10;
}
}
int main()
{
LL x;
init();
while(scanf("%lld",&x)!=EOF)
{
LL po=1,tail=0,ans=0;
int digit,i=1;
while(x)
{
digit=x%10;
x/=10;
if(digit>1) ans+=digit*dp[i-1]+po;
else if(digit==1) ans+=dp[i-1]+tail+1;
++i;
tail+=digit*po;
po*=10;
}
printf("%lld
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.