动态规划专题

在 ACM 能够开展之前，必须准备预算，并获得必要的财力支持。该活动的主要收入来自于 Irreversibly Bound Money (IBM)。思路很简单。任何时候，某位 ACM 会员有少量的钱时，他将所有的硬币投入到小猪储钱罐中。这个过程不可逆，因为只有把小猪储钱罐打碎才能取出硬币。在足够长的时间之后，小猪储钱罐中有了足够的现金，用于支付 ACM 活动所需的花费。

但是，小猪储钱罐存在一个大的问题，即无法确定其中有多少钱。因此，我们可能在打碎小猪储钱罐之后，发现里面的钱不够。显然，我们希望避免这种不愉快的情况。唯一的可能是，称一下小猪储钱罐的重量，并尝试猜测里面的有多少硬币。假定我们能够精确判断小猪储钱罐的重量，并且我们也知道给定币种的所有硬币的重量。那么，我们可以保证小猪储钱罐中最少有多少钱。

你的任务是找出最差的情形，即判断小猪储钱罐中的硬币最少有多少钱。我们需要你的帮助。不能再贸然打碎小猪储钱罐了！

输入

输入包含 T 组测试数据。输入文件的第一行，给出了 T 的值。

对于每组测试数据，第一行包含 E 和 F 两个整数，它们表示空的小猪储钱罐的重量，以及装有硬币的小猪储钱罐的重量。两个重量的计量单位都是 g (克)。小猪储钱罐的重量不会超过 10 kg (千克)，即 1 <= E <= F <= 10000 。每组测试数据的第二行，有一个整数 N (1 <= N <= 500)，提供了给定币种的不同硬币有多少种。接下来的 N 行，每行指定一种硬币类型，每行包含两个整数 P 和 W (1 <= P <= 50000，1 <= W <=10000)。P 是硬币的金额 (货币计量单位)；W 是它的重量，以 g (克) 为计量单位。

 1 #include<iostream>  
 2 #include<cstring>  
 3 #include<algorithm>   
 4 using namespace std;  
 5 int dp[10010];  
 6 int w[10010],v[10010];//w 为重量，v为价值； 
 7 int main(){  
 8     int T;  
 9     cin>>T;  
10     while(T--)
11     {
12         int n,m,c;  
13             cin>>n>>m>>c;  
14         n=m-n;  
15         for(int i=1;i<=c;i++)
16         {
17               cin>>v[i]>>w[i];
18         }  
19         for(int i=1;i<=n;i++)
20         {
21             dp[i]=1e9;
22         }
23         dp[0]=0;
24         for(int i=1;i<=c;i++){  
25             for(int j=w[i];j<=n;j++)  
26             dp[j]=min(dp[j],dp[j-w[i]]+v[i]);  
27         }  
28         if(dp[n]==1e9)   cout<<"This is impossible."<<endl;
29         else
30         {
31             cout<<"The minimum amount of money in the piggy-bank is "<<dp[n]<<"."<<endl;
32         }  
33     }
34     return 0;
35 }

View Code

数位dp模板题

求2个数的区间中没有4和62的数字的个数

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 typedef long long ll;
 6 int a[20];//分离各个数位上的数字； 
 7 int dp[20][2];//存储状态的 
 8 int dfs(int pos,int pre,int sta,bool limit)
 9 {
10     if(pos==-1)
11     {
12         return 1;
13     }
14     if(!limit&&dp[pos][sta]!=-1)
15     {
16         return dp[pos][sta];
17     }
18     int up=limit?a[pos]:9;
19     int tmp=0;
20     for(int i=0;i<=up;i++)
21     {
22         if(pre==6&&i==2)//pre代表上一位数字也就是当前状态的前一个状态； 
23         {
24             continue;
25         }
26         if(i==4)
27         {
28             continue;
29         }
30         tmp+=dfs(pos-1,i,i==6,limit&&i==a[pos]);
31     }
32     if(!limit)
33     {
34         dp[pos][sta]=tmp;
35     }
36     return tmp;
37 }
38 int solve(int x)
39 {
40     int pos=0;
41     while(x)
42     {
43         a[pos++]=x%10;
44         x/=10;
45     }
46     return dfs(pos-1,-1,0,true);
47 }
48 int main()
49 {
50     ll n,m;
51     while(cin>>n>>m)
52     {
53         if(n==0&&m==0)
54         {
55             return 0;
56         }
57         memset(dp,-1,sizeof(dp));
58         cout<<solve(m)-solve(n-1)<<endl;
59     }
60     return 0;
61 }

还有基本模板

 1 typedef long long ll;  
 2 int a[20];  
 3 ll dp[20][state];//不同题目状态不同  
 4 ll dfs(int pos,/*state变量*/,bool lead/*前导零*/,bool limit/*数位上界变量*/)//不是每个题都要判断前导零  
 5 {  
 6     //递归边界，既然是按位枚举，最低位是0，那么pos==-1说明这个数我枚举完了  
 7     if(pos==-1) return 1;/*这里一般返回1，表示你枚举的这个数是合法的，那么这里就需要你在枚举时必须每一位都要满足题目条件，也就是说当前枚举到pos位，一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */  
 8     //第二个就是记忆化(在此前可能不同题目还能有一些剪枝)  
 9     if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];  
10     /*常规写法都是在没有限制的条件记忆化，这里与下面记录状态是对应，具体为什么是有条件的记忆化后面会讲*/  
11     int up=limit?a[pos]:9;//根据limit判断枚举的上界up;这个的例子前面用213讲过了  
12     ll ans=0;  
13     //开始计数  
14     for(int i=0;i<=up;i++)//枚举，然后把不同情况的个数加到ans就可以了  
15     {  
16         if() ...  
17         else if()...  
18         ans+=dfs(pos-1,/*状态转移*/,lead && i==0,limit && i==a[pos]) //最后两个变量传参都是这样写的  
19         /*这里还算比较灵活，不过做几个题就觉得这里也是套路了 
20         大概就是说，我当前数位枚举的数是i，然后根据题目的约束条件分类讨论 
21         去计算不同情况下的个数，还有要根据state变量来保证i的合法性，比如题目 
22         要求数位上不能有62连续出现,那么就是state就是要保存前一位pre,然后分类， 
23         前一位如果是6那么这意味就不能是2，这里一定要保存枚举的这个数是合法*/  
24     }  
25     //计算完，记录状态  
26     if(!limit && !lead) dp[pos][state]=ans;  
27     /*这里对应上面的记忆化，在一定条件下时记录，保证一致性，当然如果约束条件不需要考虑lead，这里就是lead就完全不用考虑了*/  
28     return ans;  
29 }  
30 ll solve(ll x)  
31 {  
32     int pos=0;  
33     while(x)//把数位都分解出来  
34     {  
35         a[pos++]=x%10;//个人老是喜欢编号为[0,pos),看不惯的就按自己习惯来，反正注意数位边界就行  
36         x/=10;  
37     }  
38     return dfs(pos-1/*从最高位开始枚举*/,/*一系列状态 */,true,true);//刚开始最高位都是有限制并且有前导零的，显然比最高位还要高的一位视为0嘛  
39 }  
40 int main()  
41 {  
42     ll le,ri;  
43     while(~scanf("%lld%lld",&le,&ri))  
44     {  
45         //初始化dp数组为-1,这里还有更加优美的优化,后面讲  
46         printf("%lld
",solve(ri)-solve(le-1));  
47     }  
48 }

最长上升字序列：（HDU1257）

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

Input

输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)

Output

对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

Sample Input

8 389 207 155 300 299 170 158 65

Sample Output

#include<iostream>
#include<algorithm>
using namespace std;
int a[100002];
int dp[100002];
int n;
int main()
{
    while(cin>>n)
    {
        int ans=0;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            dp[i]=1;
        }
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(a[j]<a[i])
                {
                    dp[i]=max(dp[j]+1,dp[i]);//状态转移 
                }
            }
            ans=max(ans,dp[i]);//取最长的序列。 
        }
        cout<<ans<<endl;
    }
    return 0;
}

View Code