动态规划

痛并不快乐着..

数位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;
}

UVa 11021

Type: 概率

题解

有点难以理解题解的递推式,把那句f(i-1)表示i-1天后全部死亡改成f(i-1)表示i-1天后一个不生的概率可能更好理解一点吧

不知道怎么证明这个式子,思维还是不强

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;

double f[maxn],P[maxn];;
int n,k,m,T;

int main(){
    cin>>T;
    for(int i=1;i<=T;++i){
        cin>>n>>k>>m;
        for(int j=0;j<n;++j) cin>>P[j];
        f[0]=0;f[1]=P[0];
        for(int j=2;j<=m;++j){
            f[j]=0;
            for(int t=0;t<n;++t){
                f[j]+=(P[t]*pow(f[j-1],t));
            }
        }
        printf("Case #%d: %.7lf\n",i,pow(f[m],k));
    }
    return 0;
}