CQUPT 集训队专题训练（动态规划）

动态规划

A - 数位dp HDU - 2089
题意：

n，m（0<n≤m<1000000）之间有多少个满足条件的数字
1.数字的每一位不含4
2.相邻两个组成的数不能是62

解题思路：

dp[i][j]表示以j开头的i位数有多少个。首先将mn最大为7位数，初始化将满足条件的dp[i][j]求出来。
以232为例子：sum（232）=dp[3][1]+dp[2][1]+dp[2][2]+dp[1][1];求出区间(0,n)的sum(n),(0,m)的sum(m),用sum(m)-sum(n);

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int dp[10][10];
void init()
{
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=1;i<=7;i++)
    {
        for(int j=0;j<10;j++)
        {
            for(int k=0;k<10;k++)
            {
                if(j!=4&&!(j==6&&k==2))
                dp[i][j]+=dp[i-1][k];
            }
        }
    }
}
int solve(int n)
{
    int dig[10];
    int len=0;
    while(n>0)
    {
        dig[++len]=n%10;
        n/=10;
    }
    dig[len+1]=0;
    int ans=0;
    for(int i=len;i;i--)
    {
        for(int j=0;j<dig[i];j++)
        {
            if(j!=4&&!(dig[i+1]==6&&j==2))
            ans+=dp[i][j];
        }
        if(dig[i]==4||dig[i]==2&&dig[i+1]==6)
        break;
    }
    return ans;
}
int main()
{
    int l,r;
    while(scanf("%d%d",&l,&r)!=EOF&&l+r)
    {
        init();
        cout<<solve(r+1)-solve(l)<<endl;
    }
    return 0;
}

B - 概率dp HDU - 4576
题意：

一个环形跑到，被分成n个格子并且将其1到n进行标号，一个遥控汽车初始位置是1，在里面每发动一次，方向不确定的跑一次，发动m次求最后小车停在(l，r)区间的概率为多少

解题思路：

每次发动要么顺时针跑要么逆时针跑，概率各是0.5，每移动一次两边概率格子原来的概率+移动之前格子的概率*0.5.最后将l，r之间的格子的概率相加

代码：

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

C - 区间dp POJ - 1160
题意：

有v个村子在一条直线上，准备把p个邮局建在p个村子中，需要使每个村子到离他最近的邮局距离和最小，求最小的距离

解题思路：

dp[j][i]指的是在前j个村子建i个邮局距离和最小。首先在a和b村子建一个邮局的距离之和最小，应该把邮局建在（a+b)/2村子，设a=1,b=4,sum[a][b]=a[2]-a[1]+a[3]-a[2]+a[4]-a[2]=a[3]-a[1]+a[4]-a[2],当b=5时，sum[a][b]=sum[a][b-1]+a[b]-a[(a+b)/2], 则dp[v][p]为距离和最小
状态转移方程：dp[j][i]=min(dp[j][i],dp[k][i-1]+sum[k+1][j]);

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define inf 0xfffffff
using namespace std;
int dp[310][50];
int sum[310][310];
int a[310];
int main()
{
    int v,p;
    while(scanf("%d%d",&v,&p)!=EOF)
    {
        for(int i=1;i<=v;i++)
        scanf("%d",&a[i]);
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=v;i++)
        {
            for(int j=i+1;j<=v;j++)
            {
                sum[i][j]=sum[i][j-1]-a[(i+j)/2]+a[j];
            }
        }
        for(int i=1;i<=v;i++)
        {
            dp[i][1]=sum[1][i];
            dp[i][i]=0;
        }
        for(int i=2;i<=p;i++)
        {
            for(int j=i;j<=v;j++)
            {
                dp[j][i]=inf;
                for(int k=i-1;k<j;k++)
                {
                    dp[j][i]=min(dp[j][i],dp[k][i-1]+sum[k+1][j]);
                }
            }
        }
        printf("%d\n",dp[v][p]);
    }
    return 0;
}

E - 完全背包
题意：

输入数据有多组，对于每组数据第一行输入n，m，k，s(0 < n,m,k,s < 100)四个正整数。分别表示还需的经验值，保留的忍耐度，怪的种数和最多的杀怪数。接下来输入k行数据。每行数据输入两个正整数a，b(0 < a,b < 20)；分别表示杀掉一只这种怪xhd会得到的经验值和会减掉的忍耐度。(每种怪都有无数个)

解题思路：

dp[i][j]表示忍耐度为i，杀怪数为j时所得的经验值，由于每只怪可以杀多次，所以状态转移方程：           dp[i][j]=max(dp[i][j],dp[i-cnt*monst[l].na][j-cnt]+monst[l].val*cnt);
cnt指的是打这种怪的次数

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define mod 10000
using namespace std;
int dp[110][110];
struct Node
{
    int na,val;
}monst[110];
int main()
{
    int n,m,k,s;
    while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF)
    {
        for(int i=0;i<k;i++)
        {
            scanf("%d%d",&monst[i].val,&monst[i].na);
        }
        memset(dp,0,sizeof(dp));
        int i;
        for(i=1;i<=m;i++)
        {
            for(int l=0;l<k;l++)
            {
                for(int j=1;j<=s;j++)
                {
                    int cnt=1;
                    while(cnt*monst[l].na<=i&&cnt<=j)
                    {
                        dp[i][j]=max(dp[i][j],dp[i-cnt*monst[l].na][j-cnt]+monst[l].val*cnt);
                        cnt++;
                    }
                }
            }
            if(dp[i][s]>=n)
            break;
        }
        if(i>m)
        printf("-1\n");
        else
        {
            printf("%d\n",m-i);
        }
     } 
     return 0;
}