20190220总结动态规划2

绝地灬酷狼 2022-01-12 13:29 220阅读 0赞

> **感觉DP有好多东西需要补起来啊**

# 1.P1394 贴邮票\[3\] #

[**跳转到在线页面**][Link 1]

## **Description** ##

**问题1：**有 N 种不同面额的邮票，每种只有 1 张。问：可以选用多少张邮票贴出面额 K ？计算并输出需要邮票数目的**最小值**和**最大值**。

**问题2：**有 N 种不同面额的邮票，每种只有 p\[i\] 张。问：可以选用多少张邮票贴出面额 K ？计算并输出需要邮票数目的**最小值**和**最大值**。

**问题3：**有 N 种不同面额的邮票，每种邮票有无限多张。问：可以选用多少张邮票贴出面额 K ？计算并输出需要邮票数目的**最小值**和**最大值**。

## **Input** ##

第 1 行：两个整数 N 和 K，表示有N种邮票，要贴出面额 K。

第 2 行：有 N 个整数，表示有N种邮票的面额 a\[i\]。

第 3 行：有 N 个整数，表示有N种邮票的数量 p\[i\]（针对问题2）。

## **Output** ##

第 1 行：对应问题1，两个整数，表示最小值和最大值，如果无解则输出”No answer.”。

第 2 行：对应问题2，两个整数，表示最小值和最大值，如果无解则输出”No answer.”。

第 3 行：对应问题3，两个整数，表示最小值和最大值，如果无解则输出”No answer.”。

## **Sample Input** ##

5 12
    1 2 3 6 4
    1 2 1 2 1

## **Sample Output** ##

3 4 
    2 5 
    2 12

## **Hint** ##

1 <= N <= 100;　1 <= K <= 20000;　每种邮票面额不超过200。

# **分析** #

> **对于T1：**

**设 $ f\[n\]\[k\] $ 表示用 \$n\$ 种邮票贴出 \$k\$ 面额的最大和最小邮票数**

要贴出 \$k\$ 的面额，考虑是否选择第 \$n\$ 种邮票：

1.  前 \$n-1\$ 种邮票已经贴出 \$k\$ ，不选择第 \$n\$ 种
2.  前 \$n-1\$ 种邮票已经贴出 \$k-a\[n\]\$ ，选择第 \$n\$ 种

动态转移方程为：  
\\\[ max:f\[n\]\[k\]=max(f\[n-1\]\[k\]，f\[n-1\]\[k-a\[n\]\])\\\\\\\\ min:f\[n\]\[k\]=min(f\[n-1\]\[k\]，f\[n-1\]\[k-a\[n\]\]) \\\]  
可以用滚动数组优化到一维

> **对于T2：**

邮票可以选择 \$1，2，……，p\[n\]\$ 张

在T1基础上多一层循环

> **对于T3：**

邮票可以选择 \$1，2，……，\\frac\{k\}\{a\[n\]\}\$ 张

在T1基础上多一层循环

# **Codes** #

#include <bits/stdc++.h> #define INF 99999999 #define maxn 101 #define maxk 20001 using namespace std; int f11[maxk],f12[maxk]; int f21[maxk],f22[maxk]; int f31[maxk],f32[maxk]; int a[maxn],p[maxn],n,k; inline void t1() { for(int i=1;i<=k;i++) f11[i]=INF,f12[i]=-INF; for(int i=1;i<=n;i++) for(int j=k;j>=1;j--) if(j>=a[i]){ f11[j]=min(f11[j],1+f11[j-a[i]]); f12[j]=max(f12[j],1+f12[j-a[i]]); } cout<<f11[k]<<' '<<f12[k]; } inline void t2() { for(int i=1;i<=k;i++) f21[i]=INF,f22[i]=-INF; for(int i=1;i<=n;i++) for(int j=k;j>=1;j--) for(int h=1;h<=p[i];h++) if(j>=a[i]*h){ f21[j]=min(f21[j],h+f21[j-h*a[i]]); f22[j]=max(f22[j],h+f22[j-h*a[i]]); } cout<<f21[k]<<' '<<f22[k]; } inline void t3() { for(int i=1;i<=k;i++) f31[i]=INF,f32[i]=-INF; for(int i=1;i<=n;i++) for(int j=k;j>=1;j--){ int lim=k/a[i]; for(int h=1;h<=lim;h++) if(j>=a[i]*h){ f31[j]=min(f31[j],h+f31[j-h*a[i]]); f32[j]=max(f32[j],h+f32[j-h*a[i]]); } } cout<<f31[k]<<' '<<f32[k]; } int main() { #ifndef ONLINE_JUDGE freopen("testin.txt","r",stdin); freopen("testout.txt","w",stdout); #endif cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>p[i]; t1(); putchar('\n'); t2(); putchar('\n'); t3(); return 0; }

--------------------

# 2.ContestP2【USACO3.1.2】总分 #

[**跳转到在线页面**][Link 2]

## **Description** ##

学生在我们USACO的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们能尽可能的多得分，这需要你的帮助。

我们可以从几个种类中选取竞赛的题目，这里的一个“种类”是指一个竞赛题目的集合，解决集合中的题目需要相同多的时间并且能得到相同的分数。你的任务是写一个程序来告诉USACO的职员，应该从每一个种类中选取多少题目，使得解决题目的总耗时在竞赛规定的时间里并且总分最大。

输入包括竞赛的时间：M，题目种类数：N和。后面的每一行将包括两个整数来描述一个"种类": 第一个整数说明解决这种题目能得的分数(1 <= points <= 10000)，第二整数说明解决这种题目所需的时间(1 <= minutes <= 10000)。你的程序应该确定我们应该从每个"种类"中选多少道题目使得能在竞赛的时间中得到最大的分数。

来自任意的"种类"的题目数目可能是任何非负数(0或更多)。

## **Input** ##

第 1 行: M, N--竞赛的时间和题目"种类"的数目。 　　第 2-N+1 行: 两个整数:每个"种类"题目的分数和耗时。

## **Output** ##

单独的一行包括那个在给定的限制里可能得到的最大的分数。

## **Sample Input** ##

300 4
    100 60
    250 120
    120 100
    35 20

## **Sample Output** ##

605

## **Hint** ##

1 <= M <= 10,000 1 <= N <= 10,000 种题目的分数在1..10000范围内；解答所需时间在1..10000范围内

# **分析** #

一个完全背包问题，需要用压缩空间优化

（虽然不优化也只有95MB）

详见：[**P1395:背包问题\[3\]**][P1395_3]

# **Codes** #

#include <bits/stdc++.h> #define INF 2147483647 #define maxn 10001 using namespace std; int s[maxn],t[maxn]; int f[maxn]; int n,m; inline void dp() { for(int i=1;i<=m;i++) for(int j=1;j<=n;j++){ if(j>=t[i]) f[j]=max(f[j],f[j-t[i]]+s[i]); } cout<<f[n]; } int main() { #ifndef ONLINE_JUDGE freopen("testin.txt","r",stdin); freopen("testout.txt","w",stdout); #endif cin>>n>>m; for(int i=1;i<=m;i++) cin>>s[i]>>t[i]; dp(); return 0; }

--------------------

# 3.ContestP4【训练题】最大约数和 #

[**跳转到在线页面**][Link 3]

## **Description** ##

选取和不超过 S 的若干不同正整数，使得所有数的约数（不含它本身）和为最大！

## **Input** ##

一个整数 S 。

## **Output** ##

输出最大的约数之和。

## **Sample Input** ##

## **Sample Output** ##

## **Hint** ##

对于30%的数据：S<=10
    对于100%的数据：S<=1000

# **分析** #

一个 \$\\infty\$ 背包问题，要先预处理 \$\[\\;1，S\\;\]\$ 中的所有数的约数和（除开它本身，但是有 \$1\$ )

然后，\$v=n，n\\in \[1，S\]\$，\$p=\\Sigma\_\{i=1\}^n(n\\mod i=0)\$，看做 $ \\infty $ 背包问题求解

# **Codes** #

#include <bits/stdc++.h> #define maxn 1001 using namespace std; int p[maxn]; inline void init(int LIM) { // 预处理 P 数组 for(int i=2;i<=LIM;i++){ int sq=sqrt(i); for(int j=2;j<=sq;j++){ if(i%j==0){ p[i]+=(j+i/j); if(i/j==j) p[i]-=j; } } p[i]++; } } inline void dp(int LIM) { for(int i=1;i<=LIM;i++){ for(int j=1;j<=i;j++) p[i]=max(p[i],p[i-j]+p[j]); } cout<<p[LIM]; } int main() { #ifndef ONLINE_JUDGE freopen("testin.txt","r",stdin); freopen("testout.txt","w",stdout); #endif int s; cin>>s; init(s); dp(s); return 0; }

--------------------

# 4.ContestP8【训练题】多背包问题 #

[**跳转到在线页面**][Link 4]

## **Description** ##

有 N 种物品，每种只有一个，第 i 种物品的体积为 vi，重量为 wi。

现有两个背包，容量分别为为 C1 和 C2 的背包，问如何选择装入两个背包的物品，使得装入两个背包的物品的总价值尽量大。

## **Input** ##

第一行三个整数：C1、C2和N。

接下来的N行，每行两个整数，第i+1行的两个整数分别表示第i个物体的体积和重量。。

## **Output** ##

包含一行一个整数，表示背包所装物体的最大重量。

## **Sample Input** ##

8 6 5
    4 3
    2 1
    3 2
    3 4
    5 6

## **Sample Output** ##

## **Hint** ##

1<=N<=100;　　
    1<=vi<=2000;　　
    1<=c1,c2<=2000;　　
    1<=wi<=10000;

# **分析** #

一个变形的 $ 0/1 $ 背包问题，在普通的倒推求解基础上要增开一维，即：  
\\\[ f\[V\_1\]\[V\_2\]=\{\\begin\{cases\} max(f\[V\_1\]\[V\_2\]，f\[V\_1-v\[i\]\]\[V\_2\])(V\_1\\geq v\[i\])\\\\\\\\ max(f\[V\_1\]\[V\_2\]，f\[V\_1\]\[V\_2-v\[i\]\])(V\_2\\geq v\[i\]) \\end\{cases\}\}\\left(V\_1\\in \[0，C\_1\]，(V\_2\\in \[0，C\_2\]\\right) \\\]  
满足其一，执行其一，同时满足，同时执行

# **Codes** #

#include <bits/stdc++.h> #define maxc 2001 #define maxn 101 using namespace std; int f[maxc][maxc]; int c1,c2,n; int v[maxn],w[maxn]; inline void dp() { for(int i=1;i<=n;i++) for(int v1=c1;v1>=0;v1--) for(int v2=c2;v2>=0;v2--){ if(v1>=v[i]) f[v1][v2]=max(f[v1][v2],w[i]+f[v1-v[i]][v2]); if(v2>=v[i]) f[v1][v2]=max(f[v1][v2],w[i]+f[v1][v2-v[i]]); } cout<<f[c1][c2]; } int main() { #ifndef ONLINE_JUDGE freopen("testin.txt","r",stdin); freopen("testout.txt","w",stdout); #endif cin>>c1>>c2>>n; for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; dp(); return 0; }

--------------------

# 5.ContestP11【训练题】潜水员 #

[**跳转到在线页面**][Link 5]

## **Description** ##

潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸：一个为氧气，一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。

潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？

例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：

3 36 120  
10 25 129  
5 50 250  
1 45 130  
4 20 119

如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

## **Input** ##

第一行有2整数t，a（1<=t<=21，1<=a<=79）。它们表示氧，氮各自需要的量。

第二行为整数n（1<=n<=1000）表示气缸的个数。此后的n行，每行包括ti，ai，wi（1<=ti<=21，1<=ai<=79，1<=wi<=800）3整数。这些各自是：第i个气缸里的氧和氮的容量及汽缸重量。

## **Output** ##

仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。

## **Sample Input** ##

5 60
    5
    3 36 120
    10 25 129
    5 50 250
    1 45 130
    4 20 119

## **Sample Output** ##

249

## **Hint** ##

No Hint

# **分析** #

本质还是 $ 0/1 $ 背包问题，限制条件从单一元增加为二元，那么数组的维数和 \$for\$ 循环的层数也增加

**要注意当前的氧气，氮气总量超过要求量是也是合法的，所以最好是用加法由小往大推**

也即是：  
\\\[ f\[GT\]\[GA\]=min(f\[GT\]\[GA\]，f\[gt\]\[ga\]+w\[i\])\\\\\\\\其中：\\\\\\\\ GT=\\begin\{cases\}T(gt+t\[i\]>T)\\\\\\\\gt+t\[i\](gt+t\[i\]\\leq T) \\end\{cases\}，GA=\\begin\{cases\}T(ga+a\[i\]>T)\\\\\\\\ga+a\[i\](ga+a\[i\]\\leq T) \\end\{cases\} \\\]

# **Codes** #

--------------------

# 6.ontestP19【专题训练】采药 #

[**跳转到在线页面**][Link 6]

## **Description** ##

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。

医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一些询问，在给定的一段时间T内里，你可以采到草药的总价值最大是多少。”

如果你是辰辰，你能完成这个任务吗？

## **Input** ##

第一行有两个整数N（1 <= N <= 1000）和M（1 <= M <= 100），用一个空格隔开，N代表医师有N个询问，M代表山洞里的草药的数目。

接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

在接下来的N行，每行一个整数T（1 <= T <= 1000），表示医师询问的时间长度。

## **Output** ##

每个询问输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

## **Sample Input** ##

3 3
    71 100
    69 1
    1 2
    70
    71
    72

## **Sample Output** ##

3
    100
    102

## **Hint** ##

对于30%的数据，M <= 10；
    对于全部的数据，M <= 100。

# **分析** #

一个 \$0/1\$ 背包问题，要用倒推进行空间+时间优化

# **Codes** #

#include <bits/stdc++.h> #define maxn 1001 using namespace std; int t[maxn],p[maxn]; int f[maxn]; int n,m; inline void dp(int lim) { memset(f,0,sizeof(f)); for(int i=1;i<=m;i++) for(int j=lim;j>=0;j--) if(j>=t[i]) f[j]=max(f[j],f[j-t[i]]+p[i]); cout<<f[lim]; } int main() { #ifndef ONLINE_JUDGE freopen("testin.txt","r",stdin); freopen("testout.txt","w",stdout); #endif cin>>n>>m; int TIME; for(int i=1;i<=m;i++) cin>>t[i]>>p[i]; for(int i=1;i<=n;i++){ cin>>TIME; dp(TIME); putchar('\n'); } return 0; }

--------------------

# 7.ContestP20【训练题】逃亡的准备 #

[**跳转到在线页面**][Link 7]

## **Description** ##

在《Harry Potter and the Deathly Hallows》中，Harry Potter他们一起逃亡，现在有许多的东西要放到赫敏的包里面，但是包的大小有限，所以我们只能够在里面放入非常重要的物品。

现在给出该种物品的数量、体积、价值的数值，希望你能够算出怎样能使背包的价值最大的组合方式，并且输出这个数值，赫敏会非常地感谢你。

## **Input** ##

第一行有2个整数，物品种数n和背包装载体积v。　　第 2 行到 n+1 行每行3个整数，为第i种物品的数量m、体积w、价值s。

## **Output** ##

仅包含一个整数，即为能拿到的最大的物品价值总和。

## **Sample Input** ##

2 10
    3 4 3
    2 2 5

## **Sample Output** ##

## **Hint** ##

对于30%的数据：1<=v<=500、1<=n<=2000、1<=m<=10、1<=w<=20、1<=s<=100
    对于100%的数据：1<=v<=500、1<=n<=2000、1<=m<=5000、1<=w<=20、1<=s<=100

# **分析** #

一个多重背包问题，但是用倒推的方法会超时4个点……

于是 \$Perisino\$ 毅然在 \$if(j\\geq t\[i\]\\times k)\\;……\$ 的后面加上了 \$else\\;break\$，大胆而合理地提交了代码

**然后就AC了！**

这是一种新的时间优化方法吗？！（我们也不知道）

# **Codes** #

#include <bits/stdc++.h> #define INF 2147483647 #define maxn 2001 using namespace std; int s[maxn],t[maxn],num[maxn]; int f[maxn]; int n,m; inline void dp() { for(int i=1;i<=n;i++) for(int j=m;j>=1;j--){ for(int k=1;k<=num[i];k++) if(j>=t[i]*k) f[j]=max(f[j],f[j-k*t[i]]+k*s[i]); else break;// magical codes } cout<<f[m]; } int main() { #ifndef ONLINE_JUDGE freopen("testin.txt","r",stdin); freopen("testout.txt","w",stdout); #endif cin>>n>>m; for(int i=1;i<=n;i++) cin>>num[i]>>t[i]>>s[i]; dp(); return 0; }

--------------------

# 8.ContestP21 劲歌金曲 #

[**跳转到在线页面**][Link 8]

## **Description** ##

如果问一个麦霸：“你在KTV里必唱的曲目有那些？”得到的回答通常包含一首“神曲”――古巨基的《劲歌经典》。为什么呢？一般说来，KTV不会在“时间到”的时候鲁莽地把正在唱的歌切掉，而是会等它放完。例如，在还有15秒时再唱一首2分钟的歌，则实际上多唱了105秒。但是融合了37首歌曲的《劲歌经典》长达11分18秒，如果唱这首歌，相当于多唱了663秒。

假定你正在唱KTV，还剩下t秒时间。你决定下来只唱你最爱的n首歌（不含《劲歌经典》）中的一些，在时间结束之前再唱一个《劲歌金曲》，使得唱的总曲目尽量多（包含《劲歌经典》），在此前提下尽量晚的离开KTV。

## **Input** ##

第一行为在整数T，表示测试数据组数。

每组测试数据占两行，第一行为整数n和t，分别表示n首歌曲和你还剩下的时间为t秒。

第二行为n个整数，分别表示n首的时长（保证不超过3分钟）。

输入保证所有n+1首歌曲的总长度严格大于t。

## **Output** ##

每组数据输出一行，包含两个整数，分别表示你还能唱的曲目的最多数目和最大的总时长。

## **Sample Input** ##

2
    3 100
    60 70 80
    3 100
    30 69 70

## **Sample Output** ##

2 758
    3 777

## **Hint** ##

T<=100
    1<=n<=50
    1<=t<=1 000 000 000

# **分析** #

首先不要被 \$1\\leq t\\leq 1,000,000,000\$ 吓到， 题中提及每首歌市场不超过3分钟（180秒），加上 \$1\\leq n\\leq 50\$

也就是 \$1\\leq t\\leq 9,000\$ ，用 $ 0/1 $ 背包+倒推优化做

**这里注意倒推范围是 \$\[1，T-1\]\$ ，因为你要把最后一秒留给《劲歌金曲》来唱最划算**

**在推完之后要回去再扫一遍看有没有比 \$f\[T\]\$ 更大的，若有，更新 \$ans=T-1\\to ans=new\\\_max\$**

最后的时长为 $ ans+678(11\\times 60+18) $

# **Codes** #

#include <bits/stdc++.h> #define maxT 10001 #define maxn 51 #define oo 0x3f using namespace std; int f[maxT],t[maxn]; int n,T,tot; inline void dp() { memset(f,-oo,sizeof(f)); f[0]=0; for(int i=1;i<=n;i++) for(int j=tot-1;j>=0;j--){ if(j>=t[i]) f[j]=max(f[j],f[j-t[i]]+1); } int ans=tot-1; for(int i=tot-1;i>=0;i--)if(f[i]>f[ans])ans=i; cout<<f[ans]+1<<" "<<ans+678; } int main() { #ifndef ONLINE_JUDGE freopen("testin.txt","r",stdin); freopen("testout.txt","w",stdout); #endif cin>>T; while(T--){ memset(t,0,sizeof(t)); cin>>n>>tot; for(int i=1;i<=n;i++) cin>>t[i]; dp(); putchar('\n'); } return 0; }

--------------------

转载于:https://www.cnblogs.com/Ewiges-Leben/p/10409037.html

[Link 1]: http://newoj.cqyz.cn/problem/P1394
[Link 2]: http://newoj.cqyz.cn/contest/162/problem/2
[P1395_3]: http://newoj.cqyz.cn/problem/P1395
[Link 3]: http://newoj.cqyz.cn/contest/162/problem/4
[Link 4]: http://newoj.cqyz.cn/contest/162/problem/8
[Link 5]: http://newoj.cqyz.cn/contest/162/problem/11
[Link 6]: http://newoj.cqyz.cn/contest/162/problem/19
[Link 7]: http://newoj.cqyz.cn/contest/162/problem/20
[Link 8]: http://newoj.cqyz.cn/contest/162/problem/21