Gym - 100623 J Just Too Lucky(디지털 dp)
이 문제는 UVA-11361과 유사하다. 만약에 dp[u][lim][m1][m2]를 매거진 u위(낮은 것에서 높은 것까지)로 설정하면 제한을 받는지 여부, 여러분의 합이 m1이고 그 자체가 m2일 때 계속해서 아래로 매거하여 얻을 수 있는 답수를 계산하면 정확한 답을 얻을 수 있다.그러나 m2가 너무 크면 직접 상태로 보존할 수 없습니다. 여러분과 모형을 추출하면 dp의 과정에서 모형이 확실하지 않은 것을 발견할 수 있습니다. 어떻게 해야 합니까?
해결 방법은 매거 모드, 즉 매거 여러분의 k입니다. 이렇게 모드가 고정되어 쉽게 아래로 이동할 수 있습니다.경계 조건은 u<0&m1==k&m2==0이고 상태 이동 방정식은 코드를 볼 수 있습니다.
1 #include
2
3 using namespace std;
4 typedef long long ll;
5 const ll N=12+2;
6 ll bit[N],nb,d[N][2][130][130],a,b,k;
7 ll dp(ll u,ll lim,ll m1,ll m2) {
8 if(u<0) {
9 if(m1==k&&m2==0)return 1;
10 return 0;
11 }
12 ll& ret=d[u][lim][m1][m2];
13 if(~ret)return ret;
14 ret=0;
15 for(ll i=0; i<=(lim?bit[u]:9); ++i)ret+=dp(u-1,lim&&i==bit[u],m1+i,(m2*10+i)%k);
16 return ret;
17 }
18
19 ll getans(ll x) {
20 ll ans=0;
21 for(nb=0; x; x/=10)bit[nb++]=x%10;
22 for(k=1; k<=120; ++k) {
23 memset(d,-1,sizeof d);
24 ans+=dp(nb-1,1,0,0);
25 }
26 return ans;
27 }
28
29 int main() {
30 freopen("just.in","r",stdin);
31 freopen("just.out","w",stdout);
32 ll n;
33 scanf("%lld",&n);
34 printf("%lld
",getans(n));
35 return 0;
36 } 전재 대상:https://www.cnblogs.com/asdfsag/p/10350635.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
