HDU 3709 & UVALive 5004 & & ZOJ 3416 Balanced Number 디지털 dp
21189 단어 디지털 dp
문서 목록
제목의 뜻
, ( ) , [l,r] .
문제풀이
뚜렷한 디지털 dp.dp[i][j][sum]dp[i][j][sum]dp[i][j][sum]는 ii의 위치를 나타내는 숫자 중 균형점은 jj의 숫자이고 균형점 왼쪽의 모멘트는 오른쪽 모멘트의 크기를 sum sum sum의 숫자의 개수로 줄인다.균형점의 위치를 하나하나 들고, 터트리면 끝이야.
#include //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rec register char
#define rel register ll
#define gc getchar
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
inline int read(){
int x=0,f=1;char c=gc();
for (;!isdigit(c);c=gc()) f^=c=='-';
for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
return f?x:-x;
}
template <typename mitsuha>
inline bool read(mitsuha &x){
x=0;int f=1;char c=gc();
for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';
if (!~c) return 0;
for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
return x=f?x:-x,1;
}
template <typename mitsuha>
inline int write(mitsuha x){
if (!x) return 0&pc(48);
if (x<0) x=-x,pc('-');
int bit[20],i,p=0;
for (;x;x/=10) bit[++p]=x%10;
for (i=p;i;--i) pc(bit[i]+48);
return 0;
}
inline char fuhao(){
char c=gc();
for (;isspace(c);c=gc());
return c;
}
}using namespace chtholly;
using namespace std;
ll dp[25][20][1990];
int p,bit[25];
/* , , , */
ll dfs(int now,int pit,int sum,int lim){
if (!now) return !sum; // 0, ( 0)
if (!lim&&~dp[now][pit][sum]) return dp[now][pit][sum]; //
ll zxy=0; int i,j,da=lim?bit[now]:9;
for (i=0;i<=da;++i) zxy+=dfs(now-1,pit,sum+i*(now-pit),lim&&i==da); // .
return lim?zxy:dp[now][pit][sum]=zxy; // lim .
}
ll get(ll x){
ll llx=0;
for (p=0;x;x/=10) bit[++p]=x%10;
for (int i=1;i<=p;++i) llx+=dfs(p,i,0,1);
return llx-p;
}
int main(){
memset(dp,-1,sizeof dp);
for (int t=read();t--;){
ll l,r; read(l),read(r);
write(get(r)-get(l-1)),pl;
}
}
감사합니다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Gym 100623J Just To Lucky(디지털 dp)제목: 1-n 중 몇 개의 숫자가 그 자체를 만족시키고 각 수위에 의해 정제될 수 있는지; 사고방식: n은 10의 12차원이다. 곧 디지털 dp라고 생각할 수 있다. 그때는 판자가 없어서 디지털 dp를 어떻게 두드렸...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.