首页 > 代码库 > 动态规划 dp
动态规划 dp
1.洛谷 P1049 装箱问题
题目描述
有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30，每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入输出格式
输入格式：
一个整数，表示箱子容量
一个整数，表示有n个物品
接下来n行，分别表示这n 个物品的各自体积
输出格式：
一个整数，表示箱子剩余空间。
输入输出样例
2468312797
0
说明
NOIp2001普及组 第4题
思路：
f数组里记录的是最大能够存放的物体的体积，我们在输入的时候将每个物体的先在c数组中记录一下，（结合一下01背包，c数组就相当于每个物体的价值），那么同样对于每件物品我们还是有不放和放两种情况，所以转移方程就出来啦！！
f[j] = max(f[j],f[j-vi[i]]+c[i]);
(⊙v⊙)嗯~ 代码：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 5 long long V,n,vi[50]; 6 long long f[500000],c[50]; 7 8 int main() { 9 cin>>V>>n;10 for(int i=1; i<=n ;i++) {11 cin>>vi[i];12 c[i]=vi[i];13 }14 for(int i=1; i<=n; i++) {15 for(int j=V; j>=vi[i]; j--) {16 f[j] = max(f[j],f[j-vi[i]]+c[i]);17 }18 }19 cout<<V-f[V]<<endl;20 return 0;21 }
2.P1002 过河卒
题目描述
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过20的整数)，同样马的位置坐标是需要给出的。
现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入输出格式
输入格式：
一行四个数据，分别表示B点坐标和马的坐标。
输出格式：
一个数据，表示所有的路径条数。
输入输出样例
6 6 3 3
6
说明
结果可能很大！
思路：
因为马所在点和马能够一步跳跃的点是不可以走的，所以要先开个数组标记一下，（大家肯定对dx，dy数组并不陌生，所以就不介绍啦~\(≧▽≦)/~），因为从0开始会出现负数下标，所以我们从1开始，那么就将数组向右下移一格。因为卒只能往右或下跳，所以对于每个点都是由它上面的点或下面的点扩展来的，（加法原理），运用类似前缀和的做法，每个点上记录的是到达此点的路径条数，所以最后一个点上记录的就是从A到B的所有路径，输出就OK。。。
(⊙v⊙)嗯~ 代码：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 5 const long long N = 2001; 6 long long x,y,n,m,f[N][N],vis[N][N]; 7 int dx[9] = {0,2,-2,2,-2,1,-1,1,-1}; 8 int dy[9] = {0,1,1,-1,-1,2,2,-2,-2}; 9 10 int main() {11 cin>>n>>m>>x>>y;12 for(int i=0; i<=8; i++) {13 int xx=dx[i]+x,yy=dy[i]+y;14 if(xx>=0&&xx<=m&&yy>=0&&yy<=n) {15 vis[xx+1][yy+1]=1;16 }17 }18 f[1][1]=1;19 for(int i=1; i<=n+1; i++) {20 for(int j=1; j<=m+1; j++) {21 if(!vis[i][j]) {22 f[i][j]+=f[i-1][j]+f[i][j-1];23 }24 }25 }26 cout<<f[n+1][m+1]<<endl;27 return 0;28 }
3.P1004 方格取数
题目描述
设有N*N的方格图(N<=9)，我们将其中的某些方格中填入正整数，而其他的方格中则放
人数字0。如下图所示（见样例）：
A 0 0 0 0 0 0 0 0 0 0 13 0 0 6 0 0 0 0 0 0 7 0 0 0 0 0 0 14 0 0 0 0 0 21 0 0 0 4 0 0 0 0 15 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0. B某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的B
点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从A点到B点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
输入输出格式
输入格式：
输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个
表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
输出格式：
只需输出一个整数，表示2条路径上取得的最大的和。
输入输出样例
82 3 132 6 63 5 74 4 145 2 215 6 46 3 157 2 140 0 0
67
说明
NOIP 2000 提高组第四题
思路：
因为是两条路同时走，所以开了四维数组，i、j表示第一条路到达的点，l、k表示第二条路到达的点，走法又分为四种情况：
①两条路都从上边到达此点
②两条路都从左边到达此点
③第一条路从左边到达此点，第二条路由上边到达此点
④第一条路从上边到达此点，第二条路由左边到达此点
因为是要最大和，所以每种情况都取max，最后所得的也是最大。如果两条路同时经过了一个点，那么这个点就只加一次，（我是按都加上，然后如果同时经过再减去一个写的）。
(⊙v⊙)嗯，代码：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 5 const int N = 10; 6 int n,x,y,sum[N][N],ans; 7 int num[N][N],f[N][N][N][N],vis[N][N]; 8 9 int main() {10 scanf("%d",&n);11 while(scanf("%d%d",&x,&y)==2) {12 if(!x) break;13 cin>>sum[x][y];14 }15 for(int i=1; i<=n; i++) {16 for(int j=1; j<=n; j++) {17 for(int l=1; l<=n; l++) {18 for(int k=1; k<=n; k++) {19 if(i+j!=l+k) continue;20 f[i][j][l][k] = max(f[i][j][l][k],f[i-1][j][l-1][k]);21 f[i][j][l][k] = max(f[i][j][l][k],f[i][j-1][l][k-1]);22 f[i][j][l][k] = max(f[i][j][l][k],f[i-1][j][l][k-1]);23 f[i][j][l][k] = max(f[i][j][l][k],f[i][j-1][l-1][k]);24 f[i][j][l][k]+=sum[i][j]+sum[l][k];25 if(i==l&&j==k) f[i][j][l][k]-=sum[l][k];26 }27 }28 }29 }30 cout<<f[n][n][n][n]<<endl;31 return 0;32 }
自己选的路，跪着也要走完！！！
动态规划 dp