首页 > 代码库 > 各种数字三角形
各种数字三角形
数字三角形
经典例题，有记忆化搜索，正推，逆推三种方法
如果记录路径，可以开一个数组记录状态是由哪个子状态推出来的
#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>using namespace std;const int maxn = 200;int n,dp[maxn][maxn],value[maxn][maxn];int main(){ cin>>n; for(int i = 1;i <=n;i++){ for(int j = 1;j <= i;j++){ cin>>value[i][j]; } } memset(dp,-1,sizeof(dp)); for(int i = 1;i <= n;i++) dp[n][i] = value[n][i]; for(int i = n - 1;i >= 1;i--){ for(int j = 1;j <= i;j++){ dp[i][j] = value[i][j] + max(dp[i+1][j],dp[i+1][j+1]); } } cout<<dp[1][1]; return 0;}
数字三角形w
同数字三角形，要求数字总和取模100后最大，既然总和大的余数不一定大，所以转化为可行性判断
#include<iostream>#include<cstdio>#include<algorithm>using namespace std;int n,dp[50][50][105],map[50][50],ans = 0;int x,y;int main(){ cin>>n; for(int i = 1;i <= n;i++){ for(int j = 1;j <= i;j++){ scanf("%d",&map[i][j]); } } dp[1][1][map[1][1]%100] = 1; for(int i = 2;i <= n;i++){ for(int j = 1;j <= i;j++){ for(int k = 0;k <= 99;k++){ if(dp[i-1][j-1][k] || dp[i-1][j][k]){ dp[i][j][(k+map[i][j])%100] = 1; if(i == n) ans = max(ans,(k+map[i][j])%100); } } } } cout<<ans; return 0;}
数字三角形ww
同数字三角形，要求必须经过x div 2,y div 2这个点
有一个技巧，把这个点的值加上一个特别大的数，就一定会经过这个点
#include<iostream>#include<cstdio>#include<algorithm>using namespace std;int n,dp[50][50],map[50][50],ans = 0,hehe = 100000000;int main(){ cin>>n; for(int i = 1;i <= n;i++){ for(int j = 1;j <= i;j++){ scanf("%d",&map[i][j]); } } map[n/2][n/2] += hehe; for(int i = 1;i <= n;i++){ for(int j = 1;j <= i;j++){ dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]) + map[i][j]; ans = max(dp[i][j],ans); } } cout<<ans-hehe; return 0;}
数字三角形www
同上个题，只不过必过点任意
#include<iostream>#include<cstdio>#include<algorithm>using namespace std;int n,dp[50][50],map[50][50],ans = 0,hehe = 100000000;int x,y;int main(){ cin>>n; for(int i = 1;i <= n;i++){ for(int j = 1;j <= i;j++){ scanf("%d",&map[i][j]); } } cin>>x>>y; map[x][y] += hehe; for(int i = 1;i <= n;i++){ for(int j = 1;j <= i;j++){ dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]) + map[i][j]; ans = max(dp[i][j],ans); } } cout<<ans-hehe; return 0;}
最低通行费用
从左上角到右下角，往右或往下走，使沿途的权值和最小
一定要注意边界的问题
#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>using namespace std;int main(){ int map[105][105],dp[105][105],n; cin>>n; for(int i = 1;i <= n;i++){ for(int j = 1;j <= n;j++){ cin>>map[i][j]; } } for(int i = 1;i <= n;i++){ for(int j = 1;j <= n;j++){ if(i > 1 && j > 1)dp[i][j] = map[i][j] + min(dp[i-1][j],dp[i][j-1]); else if(i > 1 && j == 1) dp[i][j] = map[i][j] + dp[i-1][j]; else if(j > 1 && i == 1) dp[i][j] = map[i][j] + dp[i][j-1]; else dp[i][j] = map[i][j]; } } cout<<dp[n][n]; return 0;}
各种数字三角形
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。