我们设机器人走到(i,j) 位置时拾到最多垃圾数为 f[i][j] ，由于机器人只能朝右和下走， 只 会跟机器人上一位置拾到最多的垃圾数有关，因此很容易写出状态转移方程。 F[i][j]=max{f[i-1][j],f[i][j-1]}+a[i][j],(1<=i<=n,1<=j<=m) 初始值：f[1][i]=f[1][i-1]+a[1][i] ，f[i][1]=f[i-1][1]+a[i][1] 时间复杂度为：O(nm) 我们再来看第二问： 在最优解的情况下求方案总数， 我们只要每次在最优解的情况下统 计路径条数即可，见图 2： 设 g[i][j] 表示在位置(i,j)达到拾到 f[i][j]垃圾时的路径总数，有如下ቤተ መጻሕፍቲ ባይዱ程： g[i][j]=g[i-1][j]*x+g[i][j-1]*y 当 f[i][j]=f[i-1][j]+a[i][j] 时，x=1，否则 x=0； 当 f[i][j]=f[i][j-1]+a[i][j] 时，y=1，否则 y=0；
using namespace std; int n,m,a[200005],b[200005],f[200005]; void init() { int i,j=0; cin>>n>>m; for(i=1;i<=n;i++)cin>>a[i]; for(i=1;i<m;i++)if(a[i]<a[m])b[++j]=a[i];//去掉前面大于等于 a[m]的数 b[++j]=a[m]; for(i=m+1;i<=n;i++)if(a[i]>a[m])b[++j]=a[i];//去掉后面小于等于 a[m]的数 } int ERLIS()//上升子序列 { int i,L,r,mid,len=1; f[1]=b[1]; for(i=2;i<=n;i++) { L=1;r=len; if(f[len]<b[i]){len++;f[len]=b[i];continue;} while(L<=r) { mid=(L+r)/2; if(f[mid]<b[i])L=mid+1;else r=mid-1; } f[L]=b[i]; } return len; } int main() { init(); cout<<ERLIS()<<endl; } 3、采药 .cpp/c/pas) （medic medic.cpp/c/pas) 【问题描述】 辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最 有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都 是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间， 每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果 你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？ 【输入格式】 输入文件的第一行包含两个正整数 N,M。M 表示总共能够用来采药的时间，N 代表山 洞里的草药的数目。 接下来的 N 行每行包括两个的整数，分别表示采摘某株草药的时间 T i 和这株草药的价 值 V i。 【输出格式】 输出文件仅包含一个整数表示规定时间内可以采到的草药的最大总价值。 【样例输入输出】 medic .in medic .out medic.in medic.out 39 3 10 10 81 12 】 【数据规模和约定 数据规模和约定】 50%的数据中 N ，M≤1000；
∑
k =i
③设 f[i][j] ：表示在前 j 个村庄建立 i 个邮局所得的最小距离和。 f[1][i]=g[1][i]; f[i][j]=min{f[i-1][k]+g[k+1][j]},(2<=i<=m,i<=j<=n,i-1<=k<=j-1) #include<iostream> #include<cstdio> #include<cstring> #include <algorithm> using namespace std; int a[1005],n,m,sum[1005],g[1005][1005],f[1005][1005]; void Init() { int i,j,k,L; //n 个村庄，m 个邮局 cin>>n>>m; cin>>n>>m;//n for(i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+n+1); //先按照距离从小到大快排 for(i=1;i<=n-1;i++) //初始化 g[i][j] { g[i][i]=0; for(j=i+1;j<=n;j++)g[i][j]=g[i][j-1]+abs(a[j]-a[(i+j)/2]); } } void DP() { int i,j,k,Min; for(i=1;i<=n;i++)f[1][i]=g[1][i]; for(i=2;i<=m;i++) //阶段：邮局 for(j=i;j<=n;j++) //状态：村庄 { Min=0x7fffffff/2; for(k=i-1;k<=j-1;k++) if(Min>f[i-1][k]+g[k+1][j])Min=f[i-1][k]+g[k+1][j]; f[i][j]=Min; } cout<<f[m][n]<<endl; } int main() { Init(); DP(); system("pause"); }
100%的数据中 N ，M≤100000，Ti，V i≤10。 【题目考点】01 背包+多重背包 【思路点拨】题面虽然是最直接的 01 背包问题，但根据数据规模只能得 50 分。注意到 T 和 V 都不超不过 10 ，于是物品的种类不会超过 121。于是可以采用多重背包的算法解决该 题。 #include<fstream> using namespace std; ifstream cin("medic.in"); ofstream cout("medic.out"); int N,M,T[105],V[105],amt[105],cnt=0,f[100005],sum[11][11]; void init() { int i,j,t,v; cin>>N>>M; for(i=1;i<=N;i++){cin>>t>>v;sum[t][v]++;}//sum[t][v]时间为 t,价格为 v 的草药数量 for(i=1;i<=10;i++) for(j=1;j<=10;j++) if(sum[i][j]) { amt[++cnt]=sum[i][j];//数量 T[cnt]=i;//时间 V[cnt]=j;//价格 } } void Complete(int v,int t) { for(int i=t;i<=M;i++) if(f[i-t]+v>f[i])f[i]=f[i-t]+v; } void ZeroOne(int v,int t) { for(int i=M;i>=t;i--) if(f[i-t]+v>f[i])f[i]=f[i-t]+v; } void Mult_Pack() { for(int i=1;i<=cnt;i++) { if(amt[i]*T[i]>M){Complete(V[i],T[i]);continue;} int k=1; while(k<=amt[i]) { ZeroOne(V[i]*k,T[i]*k); amt[i]-=k; k*=2; } if(amt[i])ZeroOne(V[i]*amt[i],T[i]*amt[i]); } } int main() { init(); Mult_Pack(); cout<<f[M]<<endl; return 0; }
动态规划模拟试题 5: 10） （时间：1:40—— ——5: 5:1 1、拾垃圾的机器人 (robit.cpp/c/pas) 【问题描述】 有一块地被划分成了 n*m 个区域，在一些区域里有垃圾要拾捡。现在科研人员开发了 一个能捡垃圾的机器人， 机器人每一次都可以移动一个区域的距离， 假设机器人从最左上区 域出发， 他每次只能向右或者向下走。 每次他到达一个点， 就会自动把这个点内的垃圾拾掉。 问：该机器人最多能够拾多少垃圾？ 在最多情况下，有多少种方案？ 【输入格式】 输入文件的第一行为两个整数 n 和 m； 接下来有一个 n*m 的 01 矩阵。 矩阵中的第 i 行 j 列的数字 a[i][j]=0 表示为空地， a[i][j]=1 表示为垃圾。 【输出格式】 输出文件的第一行为一个整数，表示该机器人拾到的最多垃圾数。 第二行为一个整数，表示该机器人拾到的最多垃圾的路径总数。 【样例输入输出 1】 robit.in robit.out 33 2 100 3 000 010 【样例输入输出 2】 robit.in robit.out 67 5 0101000 11 0001010 0000000 0001001 0000000 0000010 【数据范围】n<=100,m<=100 【思路点拨】我们先看样例，如图 1，垃圾用 G 表示。假设机器人走到(i,j) 这个位置，由于 机器人只能向下向右走，那么机器人的上一个位置一定是(i-1,j)和(i,j-1)。