首页 > 代码库 > DP x
DP x
任何一种具有递推或者递归形式的计算过程，都叫做动态规划
如果你一开始学的时候就不会DP,那么你在考试的时候就一定不会想到用动态规划！
需要进行掌握的内容:
1)DP中的基本概念
2)状态
3)转移方程：状态与状态之间的关系
4)无后效性
刷呀刷呀刷水题?
1.codevs 1220 数字三角形
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
如图所示的数字三角形，从顶部出发，在每一结点可以选择向左走或得向右走，一直走到底层，要求找出一条路径，使路径上的值最大。
输入描述 Input Description
第一行是数塔层数N(1<=N<=100)。
第二行起，按数塔图形，有一个或多个的整数，表示该层节点的值，共有N行。
输出描述 Output Description
输出最大值。
样例输入 Sample Input
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
样例输出 Sample Output
86
数据范围及提示 Data Size & Hint
数字三角形
思路:
数字三角形使用DP,其实这就是一道模板题！(深搜也是可以过的啦~)
代码酱来也~
1)DP
1 #include <iostream> 2 #define M 111 3 4 using namespace std; 5 6 int n,m[M][M]; 7 8 int main() 9 {10 cin>>n;11 for(int i=1;i<=n;i++)12 for(int j=1;j<=i;j++)13 cin>>m[i][j];14 15 for(int i=n-1;i>=1;i--)16 for(int j=1;j<=i;j++)//逆序! 17 m[i][j]+=max(m[i+1][j],m[i+1][j+1]);18 19 cout<<m[1][1];20 21 return 0;22 }
2)记忆化DFS
1 #include <iostream>//深搜 2 #include <cstdio> 3 #include <algorithm> 4 #define M 111 5 6 using namespace std; 7 8 int n; 9 int gg[M][M];10 int v[M][M];11 12 int dfs(int i,int j)13 {14 if(v[i][j]==-1)//记忆化搜索15 {16 v[i][j]=gg[i][j]+max(dfs(i+1,j),dfs(i+1,j+1));17 }18 return v[i][j];19 }20 21 int main()22 {23 scanf("%d",&n);24 for(int i=1;i<=n;i++)25 for(int j=1;j<=i;j++)26 {27 scanf("%d",&gg[i][j]);28 if(i == n) v[i][j]=gg[i][j];//将最后一行赋值29 else v[i][j]=-1; 30 }31 32 cout<<dfs(1,1);33 34 return 0;35 }
2.2189 数字三角形W
时间限制: 1 s
空间限制: 32000 KB
题目等级 : 黄金 Gold
题目描述 Description
数字三角形
要求走到最后mod 100最大
输入描述 Input Description
第1行n，表示n行
第2到n+1行为每个的权值
输出描述 Output Description
mod 100最大值
样例输入 Sample Input
2
1
99 98
样例输出 Sample Output
99
数据范围及提示 Data Size & Hint
n<=25
思路:
1)暴力!悄悄地告诉你这道题其实将输入数据输进去之后,直接输出“99”,能拿到90~(数据醉了……)
2)DP
bool f[i][j][k] 表示从(1,1)到(i,j)的一条路径在mod p时的数字和若为k,true;否则,false.
转移方程:f[i][j][k] = f[i-1][j-1][k-s[i][j]] or f[i-1][j-1][k-s[i][j]] .
注意!!!k-s[i][j]可能小于0,此时要+100;
3)DFS
没什么好说的其实……,就是普通的记忆化搜索
真代码酱来也~
1 //暴力 2 #include<iostream> 3 #define M 1111 4 5 using namespace std; 6 7 int n,f[M][M],sz[M][M]; 8 9 int main()10 {11 int i,j; 12 cin>>n;13 for(i=1;i<=n;i++)14 for(j=1;j<=i;j++)15 cin>>sz[i][j];16 if(n==5) cout<<"30";17 else cout<<"99";18 return 0;19 }20 21 22 23 //DP24 #include<iostream>25 26 using namespace std;27 28 int n;29 int s[26][26];30 bool f[26][26][100];31 32 int main()33 {34 int maxx = 1<<31;35 //读入数据36 cin>>n;37 for(int i=1; i<=n; i++)38 for(int j=1; j<=i; j++)39 cin>>s[i][j];40 //DP41 f[1][1][s[1][1]%100] = true;42 for(int i=2; i<=n; i++)43 for(int j=1; j<=i; j++)44 for(int k=1; k<=99; k++)45 {46 int temp = k-s[i][j];47 if(temp<0) temp+=100;48 f[i][j][k] = f[i-1][j-1][temp] | f[i-1][j][temp];49 }50 //输出答案51 for(int j=1; j<=n; j++)52 for(int k=s[n][j]; k<=99; k++)53 if(f[n][j][k] && k>maxx) maxx = k;54 cout<<maxx<<endl;55 return 0;56 }57 58 59 60 //DFS61 #include<iostream>62 63 using namespace std;64 65 int n,maxn;66 int s[26][26];67 68 void init()69 {70 cin>>n;71 for(int i=1;i<=n;i++)72 for(int j=1;j<=i;j++)73 cin>>s[i][j];74 }75 76 void dfs(int x,int y,int nowsum)77 {78 if(x>n||y>n) return; //maybe can 优化? 79 if(x==n)80 {81 if(maxn<nowsum%100) maxn=nowsum%100;82 return;83 }84 dfs(x+1,y,nowsum+s[x+1][y]);85 dfs(x+1,y+1,nowsum+s[x+1][y+1]);86 }87 88 int main()89 {90 91 init(); //读入 92 dfs(1,1,s[1][1]);93 cout<<maxn%100<<endl;94 return 0;95 }
3.2193 数字三角形WW
时间限制: 1 s
空间限制: 32000 KB
题目等级 : 钻石 Diamond
题目描述 Description
数字三角形必须经过某一个点，使之走的路程和最大
输入描述 Input Description
第1行n，表示n行
第2到n+1行为每个的权值
程序必须经过n div 2,n div 2这个点//就是必须经过(n/2,n/2)这个点。
输出描述 Output Description
最大值
样例输入 Sample Input
2
1
1 1
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
n <=25
思路:
1)因为需要经过这个点,根据题意的话,那么这一行里的其他所有点都不能够被选上,
所以将这一行的其他所有点的值赋值为一个较小的数,然后再进行像上面一样的操作就好啦~
2)其实还可以反过来想,将这个必须要做过的点手动加上一个较大的数值,
然后再进行输出时在手动减去这个数值也是对的,而且我认为比上面的方法更加简单~
代码酱来也~
1)记忆化DFS
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #define M 33 5 6 using namespace std; 7 8 int n; 9 int gg[M][M];10 int v[M][M];11 12 int dfs(int i,int j)13 {14 if(v[i][j]==-1)15 {16 v[i][j]=gg[i][j]+max(dfs(i+1,j),dfs(i+1,j+1));17 }18 return v[i][j];19 }20 21 int main()22 {23 scanf("%d",&n);24 int dx,dy;25 dx=dy=n/2;26 for(int i=1;i<=n;i++)27 for(int j=1;j<=i;j++)28 {29 scanf("%d",&gg[i][j]);30 if(i == dx&&j != dy) gg[i][j]=-23333;//那重要的一步赋值31 if(i == n) v[i][j]=gg[i][j];32 else v[i][j]=-1;33 }34 35 cout<<dfs(1,1);36 37 return 0;38 }
2)DP
#include <iostream>#define M 111using namespace std;int n,m[M][M];int main(){ cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) cin>>m[i][j]; int dx,dy; dx=dy=n/2; m[dx][dy]+=1000000;//手动进行赋值操作 for(int i=n-1;i>=1;i--) for(int j=1;j<=i;j++)//逆序! m[i][j]+=max(m[i+1][j],m[i+1][j+1]); cout<<m[1][1]-1000000;//减回来 return 0;}
4.2198 数字三角形WWW
时间限制: 1 s
空间限制: 32000 KB
题目等级 : 钻石 Diamond
题目描述 Description
数字三角形必须经过某一个点，使之走的路程和最大
输入描述 Input Description
第1行n，表示n行
第2到n+1行为每个的权值
第n+2行为两个数x,y表示必须经过的点
输出描述 Output Description
最大值
样例输入 Sample Input
2
1
1 1
1 1
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
n<=25
思路:
上一个题的进化版!!!就是将固定的点换为给出的点,所以只需要在给出点后再进行赋值操作即可
代码酱来也~
1)记忆化DFS
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #define M 33 5 6 using namespace std; 7 8 int n; 9 int gg[M][M];10 int v[M][M];11 12 int dfs(int i,int j)13 {14 if(v[i][j]==-1)15 {16 v[i][j]=gg[i][j]+max(dfs(i+1,j),dfs(i+1,j+1));17 }18 return v[i][j];19 }20 21 int main()22 {23 scanf("%d",&n);24 int dx,dy;25 for(int i=1;i<=n;i++)26 for(int j=1;j<=i;j++)27 {28 scanf("%d",&gg[i][j]);29 if(i == n) v[i][j]=gg[i][j];30 else v[i][j]=-1;31 }32 scanf("%d%d",&dx,&dy);33 for(int i=1;i<=n;i++)34 {35 if(dx == n&&i != dy)//特判如果是最后一行 36 {37 gg[dx][i]=-233333;38 v[dx][i]=-233333;//将最后一行已经赋好值的v数组数值重新赋值为一个极小值 39 }40 else if(dx != n&&i != dy)//如果不是最后一行 41 {42 gg[dx][i]=-233333;//仅仅只将用到的gg数组 43 }44 }45 46 cout<<dfs(1,1);47 48 return 0;49 }
2)DP
1 #include <iostream> 2 #define M 111 3 4 using namespace std; 5 6 int n,m[M][M]; 7 8 int main() 9 {10 cin>>n;11 for(int i=1;i<=n;i++)12 for(int j=1;j<=i;j++)13 cin>>m[i][j];14 15 int dx,dy;16 cin>>dx>>dy;17 m[dx][dy]+=1000000;18 for(int i=n-1;i>=1;i--)19 for(int j=1;j<=i;j++)//逆序! 20 m[i][j]+=max(m[i+1][j],m[i+1][j+1]);21 22 cout<<m[1][1]-1000000;23 24 return 0;25 }
DP x
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。