HDU3555-Bomb(디지털 DP)
<span style="font-size:18px;">#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
typedef __int64 LL;
using namespace std;
LL dp[25][3];
void Init()
{
memset(dp,0,sizeof dp);
dp[0][0]=1;
for(int i=1;i<=20;i++){
dp[i][0]=dp[i-1][0]*10-dp[i-1][1];
dp[i][1]=dp[i-1][0];
dp[i][2]=dp[i-1][2]*10+dp[i-1][1];
}
}
int main()
{
Init();
int t;
cin>>t;
while(t--){
LL n;
scanf("%I64d",&n);
n++;
int num[21],k=0;
while(n){
num[++k]=n%10;
n/=10;
}
LL ans=0;
int flag=0,pre=0;
for(int i=k;i>=1;i--){
ans+=dp[i-1][2]*num[i];
if(!flag&&num[i]>4){
ans+=dp[i-1][1];
}
if(flag){
ans+=dp[i-1][0]*num[i];
}
if(pre==4&&num[i]==9){
flag=1;
}
pre=num[i];
}
printf("%I64d
",ans);
}
return 0;
}</span>
기억형 검색:
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef __int64 LL;
LL dp[20][3], N;
int num[20];
LL dfs(int pos, int statu, int limit)
{
if (pos == -1) { // , 49
return statu == 2;
}
if (!limit && dp[pos][statu] != -1) return dp[pos][statu]; //
LL sum = 0;
int s, end = limit ? num[pos] : 9; //
for (int i = 0; i <= end; ++i) { //
s = statu;
if (statu == 1 && i == 9) s = 2;
if (statu == 0 && i == 4) s = 1;
if (statu == 1 && i != 4 && i != 9) s = 0;
sum += dfs(pos-1, s, limit && i == end);
}
return limit?sum:dp[pos][statu]=sum;
}
LL Cal(LL n)
{
int pos = 0;
while (n != 0) {
num[pos++] = n % 10;
n /= 10;
}
return dfs(pos-1, 0, 1);
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
memset(dp, -1, sizeof (dp));
scanf("%I64d", &N);
printf("%I64d
", Cal(N));
}
return 0;
}<span style="color:#ff0000;">
</span>
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.