动态规划合集（一）

我会带着你远行 2021-12-09 20:45 359阅读 0赞

# 探索数字迷塔 #

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//程序名:新的C++程序
    //作者: 
    
    #include<iostream>
    #include<fstream>
    #include<algorithm>
    using namespace std;
    int n,a[1005][1005],f[1005][1005];
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            for(int j=1; j<=i; j++)cin>>a[i][j],f[i][j]=a[i][j];
        for(int i=n-1;i>=1;i--)
            for(int j=1;j<=i;j++)f[i][j]=f[i][j]+max(f[i+1][j],f[i+1][j+1]);
        cout<<f[1][1];
        return 0;
    }

# 圣诞树 #

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//程序名:新的C++程序
    //作者: 
    
    #include<iostream>
    #include<fstream>
    #include<algorithm>
    
    using namespace std;
    int n,a[101],b[101][101],f[101],ans;
    void scanf()
    {
        char c;
        cin>>n;
        c=getchar();
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            int l=0,x=0;
            while((c=getchar())!='\n')
            {
                if(c==' ')
                {
                    if(l)b[i][++x]=l,l=0;
                }
                else l=l*10+c-'0';
            }
            if(l)b[i][++x]=l;
        }
    }
    int main()
    {
        scanf();
        for(int i=n;i>=1;i--)
        {
            int maxx=0;
            for(int j=1;b[i][j];j++)maxx=max(maxx,f[b[i][j]]);
            f[i]=a[i]+maxx;
            ans=max(f[i],ans);
        }
        cout<<ans;
        return 0;
    }

# 传球游戏 #

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//程序名:新的C++程序
    //作者: 
    
    #include<iostream>
    #include<fstream>
    #include<algorithm>
    
    using namespace std;
    int n,m,f[31][31];
    int main()
    {
        cin>>n>>m;
        f[1][0]=1;
        for(int i=1;i<=m;i++)
        {
            for(int j=2;j<=n-1;j++)f[j][i]+=f[j+1][i-1]+f[j-1][i-1];
            f[1][i]=f[2][i-1]+f[n][i-1];
            f[n][i]=f[1][i-1]+f[n-1][i-1];
        }
        cout<<f[1][m];
        return 0;
    }

# 黑熊过河 #

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//程序名:新的C++程序
    //作者: 
    
    #include<iostream>
    #include<fstream>
    #include<algorithm>
    
    using namespace std;
    int a[100000],dp[100000],p,q,n;
    int main()
    {                             
        cin>>p>>q>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        dp[0]=p;
        if(p>q)dp[1]=p-q+a[1];
        else dp[1]=-1;
        for(int i=2;i<=n+1;i++)
        {
            bool f=0;
            if(dp[i-1]-q>=0)dp[i]=max(dp[i],dp[i-1]-q+a[i]),f=1;
            if(dp[i-2]-q>=0)dp[i]=max(dp[i],dp[i-2]-q+a[i]),f=1;
            if(!f)dp[i]=-1;
        }
        if(dp[n+1]<0)cout<<"NO";
        else cout<<dp[n+1];
        return 0;      
    }

#  抢金块 #

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//程序名:新的C++程序
    //作者: 
    
    #include<iostream>
    #include<fstream>
    #include<algorithm>
    
    using namespace std;
    int n,s,t,a[1005],dp[1005];
    int main()
    {
        cin>>n>>s>>t;
        for(int i=1;i<=n;i++)cin>>a[i];
        dp[1]=a[1];
        for(int i=2;i<=n;i++)
        {
            int maxx=0;
            for(int j=s;j<=t;j++)if(i-j>0)maxx=max(maxx,dp[i-j]+a[i]);
            dp[i]=maxx;
        }
        cout<<dp[n];
        return 0;
    }

#  维修栅栏 #

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//程序名:新的C++程序
    //作者: 
    
    #include<iostream>
    #include<fstream>
    #include<algorithm>
    #include<cmath>
    #include<cstdio>
    
    using namespace std;
    int n,t,p;
    int a[2505];
    double dp[2505][2505];
    double ans=1<<29;
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++){cin>>p;if(!p)a[++t]=i;}
        for(int i=1;a[i];i++)
        {
            for(int j=1;j<=i;j++)
            {
                dp[i][j]=1<<29;
                if(j==1)dp[i][j]=sqrt(a[i] - a[j] + 1);
                else for(int k=j-1;k<i;k++)dp[i][j]=min(dp[i][j],dp[k][j-1]+sqrt(a[i]-a[k+1]+1));    
                if(!a[i+1])ans=min(ans,dp[i][j]);
            }
        }    
        if(ans==1<<29)cout<<"0.000";
        else printf("%.3f",ans);
        return 0;
    }

#  攀登宝塔 #

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//程序名:新的C++程序
    //作者: 
    
    #include<iostream>
    #include<fstream>
    #include<algorithm>
    
    using namespace std;
    int n,a[10005],dp[10005][2];
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        dp[1][1]=a[1];
        for(int i=2;i<=n;i++)
        {
            dp[i][0]=min(dp[i-1][1],dp[i-2][1]);
            dp[i][1]=min(dp[i-1][0],dp[i-1][1])+a[i];
        }
        cout<<min(dp[n][0],dp[n][1])<<endl;
        return 0;
    }

# 最大价值 #

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//程序名:新的C++程序
    //作者: 
    
    #include<iostream>
    #include<fstream>
    #include<algorithm>
    #include<cstdio>
    using namespace std;
    int n,a[105];
    double dp[105][2];
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        dp[1][0]=100; 
        dp[1][1]=a[1];
        for (int i=2;i<=n;i++)
        {
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]/a[i]*100);
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]*a[i]/100);
        }
        printf("%.2f",max(dp[n][0],dp[n][1]/a[n]*100));
        return 0;
    }

# 桐桐的爬山计划 #

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//程序名:新的C++程序
    //作者: 
    
    #include<iostream>
    #include<fstream>
    #include<cstring>
    
    using namespace std;
    int n,a[105],dp[105][10005];
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=0;i<=100;i++)
            for(int j=0;j<=10000;j++)dp[i][j]=10001;
        dp[0][0]=0;
        for(int i=1;i<=n;i++)
            for(int j=0;j<=10000;j++)
            {
                int w=j-a[i]<0?10001:dp[i-1][j-a[i]];
                dp[i][j]=min(max(w,j),dp[i-1][j+a[i]]);
            }
        if(dp[n][0]==10001)cout<<"IMPOSSIBLE";
        else cout<<dp[n][0]+2; 
        return 0;
    }

# 多米诺骨牌 #

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//程序名:新的C++程序
    //作者: 
    #include<iostream>
    #include<fstream>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int n,up[1005],down[1005],sum,mup,dp[6001],ans;
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>up[i]>>down[i];
            sum+=up[i]+down[i];
            mup+=up[i];
        }
        for(int i=0;i<=6000;i++)dp[i]=-1;
        dp[mup]=0;
        for(int i=1;i<=n;i++)
        {
            if(up[i]<down[i])mup+=down[i]-up[i];
            if(up[i]>=down[i])for(int j=0;j<=mup-up[i]+down[i];j++){
         if(dp[j-down[i]+up[i]]!=-1)dp[j]=min((dp[j]==-1?n+1:dp[j]),dp[j-down[i]+up[i]]+1);}
            else for(int j=mup;j>=down[i]-up[i];j--){
         if(dp[j-down[i]+up[i]]!=-1)dp[j]=min((dp[j]==-1?n+1:dp[j]),dp[j-down[i]+up[i]]+1);}
        }
        for(int i=1;i<=mup;i++)if(abs(sum-i*2)<abs(sum-ans*2)||abs(sum-i*2)==abs(sum-ans*2)&&dp[i]<dp[ans])ans=i;
        cout<<dp[ans];
        return 0;
    }

转载于:https://www.cnblogs.com/2006hanziwei/p/11179725.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211209/1edfc4170ba74523b7680bda6a0e188f.png