动态规划

痛并不快乐着..

数位dp

HDU 3555

不要49

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

LL dp[20][3];
int digit[20];

LL dfs(int pos,int pre,int state,bool jud){
    //cout<<pos<<" "<<state<<endl;
    ///数位递归到0则返回
    if(pos==0)
        return 1;
    ///如果有数据就返回数据
    if(!jud&&dp[pos][state]!=-1)
        return dp[pos][state];

    LL ans=0;
    int ed=jud?digit[pos]:9;
    //cout<<ed<<endl;
    for(int i=0;i<=ed;++i){
        if(pre==4&&i==9)continue;
        ans+=dfs(pos-1,i,i==4,jud&&i==ed);
    }
    if(!jud){///不取上界时,可以取满
        dp[pos][state]=ans;
    }
    return ans;
}

///数字处理函数
LL cal(LL x){
    int pos=0;
    while(x){
        digit[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,0,0,true);
}

int main(){
    memset(dp,-1,sizeof(dp));
    int T;
    for(scanf("%d",&T);T;T--){
        LL n;
        scanf("%lld",&n);
        printf("%lld\n",n-cal(n)+1);
    }
    return 0;
}

HDU 2089

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1000000+7;
LL dp[20][3];
int digit[20];

LL dfs(int pos,int pre,int state,bool jud){
    //cout<<pos<<" "<<state<<endl;
    ///数位递归到0则返回
    if(pos==0)
        return 1;
    ///如果有数据就返回数据
    if(!jud&&dp[pos][state]!=-1)
        return dp[pos][state];

    LL ans=0;
    int ed=jud?digit[pos]:9;//这句是判断他的上界
    //cout<<ed<<endl;
    for(int i=0;i<=ed;++i){
        if(pre==6&&i==2)continue;
        if(i==4)continue;
        ans+=dfs(pos-1,i,i==6,jud&&i==ed);
    }
    if(!jud){///不取上界时,可以取满
        dp[pos][state]=ans;
    }
    return ans;
}

///数字处理函数
LL cal(LL x){
    int pos=0;
    //cout<<"tx: ";
    while(x){
        digit[++pos]=x%10;
        //cout<<x%10<<endl;
        x/=10;
    }
    return dfs(pos,0,0,true);
}

int main(){
    memset(dp,-1,sizeof(dp));
    LL n,m;
    while(~scanf("%lld%lld",&n,&m) && n+m){
        printf("%lld\n",cal(m)-cal(n-1));
    }
    return 0;
}

「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛 (重现) A

【题目来源】

「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛 (重现) A

【Tip】

找进位规律找的自己恶心吐了,最后跪在了百位进位时忘了加最后的那几次十进位…(最后也是对拍了一个ACcode才找到了错误的地方

思维漏洞还是太大了,或者说这种思维方式不太好.

不过也算是又学会了一点东西.

【My Code】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
int main(){
    freopen(“in_2.txt”, “r”, stdin);
    freopen(“out_2.txt”, “w”, stdout);
    int T,N,M,B,C,EndN,EndM;
    while(~scanf(“%d”,&T)){
        int ca=1;
        while(T–){
            int REG1,REG2,D1,D2,ans=-INF,r1[3],r2[3],r11[3],r22[3];
            D1=D2=0;
            scanf(“%d%d”,&B,&C);
            REG1=B;
            REG2=C;
            red(i,2,0){
                r1[i]=REG1%10;REG1/=10;
                r2[i]=REG2%10;REG2/=10;
            }
            scanf(“%d”,&N);
            rep(i,N+1){//甲得i分,乙得M分
                int D11,D22,all;
                D11=D22=0;all=0;
                M=N-i;
                EndN=B+i;
                EndM=C+M;
                red(i,2,0){
                    r11[i]=EndN%10;EndN/=10;
                    r22[i]=EndM%10;EndM/=10;
                }//百位进位19 十位进位9
                r11[0]=r11[0]-r1[0];
                if(r11[0]) {
                    r11[1]=(r11[0]-1)*9+(9-r1[1])+r11[1];
                    all+=(r11[0]*18+r11[1]*9);
                }else{
                    r11[1]=r11[1]-r1[1];
                    all+=(r11[1]*9);
                }
                r22[0]=r22[0]-r2[0];
                if(r22[0]) {
                    r22[1]=(r22[0]-1)*9+(9-r2[1])+r22[1];
                    all+=(r22[0]*18+r22[1]*9);
                }else{
                    r22[1]=r22[1]-r2[1];
                    all+=(r22[1]*9);
                }
               // printf(“%d\n”,all+N);
                ans=max(ans,all+N);
            }
            printf(“Case %d: %d\n”,ca++,ans);
        }
    }
    return 0;
}

【效率&直观 code】

感觉处理方法类似于数位dp

    #include<bits/stdc++.h>
    using namespace std;
    #define maxn 1005
    int dp[maxn];

    void init(){
        for(int i=1;i<=999;i++){
            if(i%100==0){
                dp[i]=dp[i-1]+19;
            }else if(i%10==0)
                dp[i]=dp[i-1]+10;
            else
                dp[i]=dp[i-1]+1;
        }
        return;
    }

    int main(){
        freopen(“in_2.txt”, “r”, stdin);
        freopen(“out_3.txt”, “w”, stdout);
        int T;
        cin>>T;
        init();
        for(int cas=1;cas<=T;cas++){
            int a,b,k;
            cin>>a>>b>>k;
            int ans=0;
            int tans=0;
            for(int i=0;i<=k;i++){
                tans=dp[a+i]-dp[a]+dp[b+k-i]-dp[b];
               // printf(“%d\n”,tans);
                ans=max(ans,tans);
            }
            cout<<“Case “<<cas<<“: “;
            cout<<ans<<“\n”;
        }
        return 0;
    }

【数据 in_2.txt】

13
000 000
1
000 000
10
000 000
100
001 000
109
001 001
109
123 123
89
458 253
500
327 652
200
320 602
58
227 725
63
102 103
37
023 001
900
21 23
5

【输出】

Case 1: 1
Case 2: 19
Case 3: 199
Case 4: 217
Case 5: 217
Case 6: 179
Case 7: 1013
Case 8: 398
Case 9: 112
Case 10: 126
Case 11: 73
Case 12: 1791
Case 13: 5

HDU 2098

【类型】

数位dp入门

【Tip】

一个blog

一个ppt

【Code】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
/*  ////////////////////////   C o d i n g  S p a c e   ////////////////////////  */
const int maxn=7;
int dp[maxn][10];
int d[maxn],N,M;
void init(){
    dp[0][0] = 1;
    for (int i = 1; i <= 7; ++i)
        for (int j = 0; j <= 9; ++j)
            for (int k = 0; k <= 9; ++k)
                if (j != 4 && !(j == 6 && k == 2))
                    dp[i][j] += dp[i – 1][k];
}

int solve(int num){
    int ans=0,len=0;
    while(num>0){
        d[++len]=num%10;
        num/=10;
    }
    d[len+1]=0;
    for(int i=len;i>=1;–i){
        for(int j=0;j<d[i];++j){
            if(j!=4 && !(d[i+1]==6 && j==2))
                ans+=dp[i][j];
        }
        if(d[i]==4 || (d[i+1]==6 && d[i]==2))
            //已经出现4,62如,d[i]为4
            //那么就不必再计算第i位为4的情况了.
            break;
    }
    return ans;
}

int main(){
//   #ifndef DEF
//      freopen(“out.txt”,”w”,stdout);
//   #endif // DEF
    init();
    while(~SII(N,M) && N+M){
        printf(“%d\n”,solve(M+1)-solve(N));
    }
    return 0;
}