当前位置:网站首页>数字三角形模型 AcWing 275. 传纸条
数字三角形模型 AcWing 275. 传纸条
2022-07-07 06:11:00 【T_Y_F666】
数字三角形模型 AcWing 275. 传纸条
原题链接
算法标签
动态规划 线性DP
思路
行数取值范围优化
代码
#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
const int N = 105;
int f[2*N][N][N], a[N][N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void put(int x) {
if(x<0) putchar('-'),x=-x;
if(x>=10) put(x/10);
putchar(x%10^48);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n=read(),m=read();
rep(i, 1, n+1){
rep(j, 1, m+1){
a[i][j]=read();
}
}
// 行列值之和 由行确定列
rep(k, 2, n+m+1){
// 第一次第i行
rep(i1, 1, n+1){
// 第二次第i行
rep(i2, 1, n+1){
// j1表示第一次第j列 j2表示第二次第j列
int j1=k-i1, j2=k-i2;
if(j1>=1&&j1<=m&&j2>=1&&j2<=m){
int t=a[i1][j1];
if(i1-i2){
t+=a[i2][j2];
}
f[k][i1][i2]=max({f[k][i1][i2], f[k-1][i1-1][i2-1]+t, f[k-1][i1-1][i2]+t, f[k-1][i1][i2-1]+t, f[k-1][i1][i2]+t});
}
}
}
}
printf("%lld", f[n+m][n][n]);
return 0;
}
行数取值范围优化代码
#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
const int N = 105;
int f[2*N][N][N], a[N][N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void put(int x) {
if(x<0) putchar('-'),x=-x;
if(x>=10) put(x/10);
putchar(x%10^48);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n=read(),m=read();
rep(i, 1, n+1){
rep(j, 1, m+1){
a[i][j]=read();
}
}
// 行列值之和 由行确定列
rep(k, 2, n+m+1){
// 第一次第i行
rep(i1, max(1ll, k-m), min(k, n)+1){
// 第二次第i行
rep(i2, max(1ll, k-m), min(k, n)+1){
// k-i1表示第一次列数 k-i2表示第二次列数
int t=a[i1][k-i1];
if(i1-i2){
t+=a[i2][k-i2];
}
f[k][i1][i2]=max({f[k][i1][i2], f[k-1][i1-1][i2-1]+t, f[k-1][i1-1][i2]+t, f[k-1][i1][i2-1]+t, f[k-1][i1][i2]+t});
}
}
}
printf("%lld", f[n+m][n][n]);
return 0;
}
原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈
边栏推荐
- Input and output of floating point data (C language)
- Three usage scenarios of annotation @configurationproperties
- mysql分区讲解及操作语句
- 数据分析方法论与前人经验总结2【笔记干货】
- GOLand idea intellij 无法输入汉字
- 调用华为游戏多媒体服务的创建引擎接口返回错误码1002,错误信息:the params is error
- [Yugong series] February 2022 U3D full stack class 008 - build a galaxy scene
- [南京大学]-[软件分析]课程学习笔记(一)-introduction
- 对API接口或H5接口做签名认证
- Virtual address space
猜你喜欢
联想混合云Lenovo xCloud:4大产品线+IT服务门户
Download and install orcale database11.2.0.4
let const
IP地址的类别
Opencv learning notes II - basic image operations
Rapid integration of authentication services - harmonyos platform
leetcode135. Distribute candy
[Yugong series] February 2022 U3D full stack class 005 unity engine view
Three series of BOM elements
AVL平衡二叉搜索树
随机推荐
How to integrate app linking services in harmonyos applications
指针进阶,字符串函数
opencv之图像分割
Category of IP address
Required String parameter ‘XXX‘ is not present
Greenplum6.x重新初始化
A bug using module project in idea
Redis summary
Image segmentation in opencv
Installation and configuration of PLSQL
Golan idea IntelliJ cannot input Chinese characters
Greenplum6.x常用语句
路由信息协议——RIP
Greenplum6.x-版本变化记录-常用手册
Iptables' state module (FTP service exercise)
Appeler l'interface du moteur de création du service multimédia de jeu Huawei renvoie le Code d'erreur 1002, le message d'erreur: les paramètres sont l'erreur
[Yugong series] February 2022 U3D full stack class 006 unity toolbar
说一个软件创业项目,有谁愿意投资的吗?
Implementation method of data platform landing
The single value view in Splunk uses to replace numeric values with text