2016寒假集训队第七次作业

题解

Problem A:数位dp

题意：中文题

题解：dp[i][j] 表示符合i位数，并最高为j的所有解，当j!=4时，dp[i][j]=dp[i-1][0]+dp[]i-1][1]+…………+dp[i-1][9]。按照状态方程就可以完成。

参考代码：

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int a[1000000],n,m;
int fun(int x)
{
    while(x)
    {
        if (x%10==4)
            return 0;
        if (x%100==62)
            return 0;
        x/=10;
    }
    return 1;
}
int main()
{
    a[0]=0;
    for (int i=1; i<=1000000; i++)
        if(fun(i))
            a[i]=a[i-1]+1;
        else
            a[i]=a[i-1];
    while(cin>>n>>m)
    {
        if (m==0 && n==0) break;
        cout<<a[m]-a[n-1]<<endl;
    }
    return 0;
}

Problem B:概率dp

题意：绕圆(1～n)行走，有m个命令，随机选择方向，第i个命令行走mi个距离。求在l到r的范围内的概率。

题解：构造两个数组，b[]记录前一个状态，a[]记录当前状态(其初始化为0)，将不为0的b[]，进行移动，然后加到目的位置的a[]中。最后输出ans=b[l]+...+b[r]。

参考代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
double a[210],b[210],ans;
int n,m,l,r,sum1,w,sum2,pos;
int main()
{
    while(cin>>n>>m>>l>>r)
    {
        if (m==0 && n==0 && l==0 && r==0) break;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        b[1]=1;
        for (int i=1; i<=m; i++)
        {
            scanf("%d",&w);
            for (int j=1; j<=n; j++)
            {
                if (b[j]==0) continue;
                pos=j+w%n;
                if (pos>n) pos-=n;
                a[pos]+=0.5*b[j];
                pos=j-w%n;
                if (pos<=0) pos+=n;
                a[pos]+=0.5*b[j];
            }
            for (int j=1; j<=n; j++)
            {
                b[j]=a[j];
                a[j]=0;
            }
        }
        sum1=0;
        sum2=0;
        ans=0;
        for (int i=l; i<=r; i++)
        {
            ans+=b[i];
        }
        printf("%.4lf\n",ans);
    }
    return 0;
}

Problem C:区间dp

题意：在v个村庄中建立p个邮局，求所有村庄到它最近的邮局的距离和，村庄在一条直线上，邮局建在村庄上。

题解：首先求出在连续的几个村庄上建立一个邮局的最短距离，用数组dis[i][j]表示在第i个村庄和第j个村庄之间建一个邮局的最短距离。dis[i][j]=dis[i][j-1]+x[j]-x[(i+j)/2];（x[i]为坐标）。用数组dp[i][j]表示在前i个村庄中建立j个邮局的最小距离。即在前k个村庄建立j-1个邮局，在k+1到j个村庄建立一个邮局。

方程：dp[i][j]=min(dp[i][j],dp[k][j-1]+dis[k+1][i])

参考代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int dp[310][35],dis[310][310],x[310],v,p;
int main()
{
    while(cin>>v>>p)
    {
        if (v==-1 && p==-1) break;
        for (int i=1; i<=v; i++)
            scanf("%d",&x[i]);
        for (int i=1; i<=v; i++)
        {
            for (int j=i+1; j<=v; j++)
            {
                dis[i][j]=dis[i][j-1]+x[j]-x[(i+j)/2];
            }
        }
        for (int i=1; i<=v; i++)
        {
            dp[i][i]=0;
            dp[i][1]=dis[1][i];
        }
        for (int j=2; j<=p; j++)
        {
            for(int i=j+1; i<=v; i++)
            {
                dp[i][j]=1000000000;
                for (int k=j-1; k<i; k++)
                {
                    dp[i][j]=min(dp[i][j],dp[k][j-1]+dis[k+1][i]);
                }
            }
        }
        cout<<dp[v][p]<<endl;
    }
    return 0;
}

Problem E:完全背包

题解：先求出不超过他的忍耐度杀完s只怪时能够得到的经验值，
如果能升完最后一级，再求用去多少忍耐度就能够升级，最后用他的忍耐度减去需要消耗的忍耐度即可。

方程：f[i][j]=max{f[i][j],f[i-b][j-1]+a}（i表示忍耐度，j表示杀怪数）

参考代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int dp[110][110],a[110],b[110],n,m,k,s;
int main()
{
    while(cin>>n>>m>>k>>s)
    {
        for (int i=0; i<k; i++)
            scanf("%d%d",&a[i],&b[i]);
        memset(dp,0,sizeof(dp));
        for (int i=0; i<k; i++)
            for (int j=b[i]; j<=m; j++)
                for (int l=1; l<=s; l++)
                    dp[j][l]=max(dp[j][l],dp[j-b[i]][l-1]+a[i]);
        if (dp[m][s]>=n)
        {
            for (int i=0; i<=m; i++)
                if(dp[i][s]>=n)
                {
                    cout<<m-i<<endl;
                    break;
                }
        }
        else cout<<"-1"<<endl;
    }
    return 0;  
}