当前位置:网站首页>数字三角形模型 AcWing 1027. 方格取数
数字三角形模型 AcWing 1027. 方格取数
2022-07-07 06:11:00 【T_Y_F666】
数字三角形模型 AcWing 1027. 方格取数
原题链接
算法标签
DP 线性DP
思路
错误思路:分两次走
由于第一次走时可能存在多条路径都是第一次的解集,分开走只能选择其中的一条。但第一次走过的地方会被重置成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];
int aa, b, c, d;
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();
while(aa=read(), b=read(), c=read(), aa||b||c){
a[aa][b]=c;
}
// 行列值之和 由行确定列
rep(k, 2, n+n+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<=n&&j2>=1&&j2<=n){
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[2*n][n][n]);
return 0;
}
原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈
边栏推荐
- [machine learning] watermelon book data set_ data sharing
- Download and install orcale database11.2.0.4
- JEditableTable的使用技巧
- Componentspace2022, assertions, protocols, bindings, and configuration files
- JS的操作
- 调用华为游戏多媒体服务的创建引擎接口返回错误码1002,错误信息:the params is error
- 指针进阶,字符串函数
- Rapid integration of authentication services - harmonyos platform
- MySQL introduction - crud Foundation (establishment of the prototype of the idea of adding, deleting, changing and searching)
- 关于基于kangle和EP面板使用CDN
猜你喜欢
调用华为游戏多媒体服务的创建引擎接口返回错误码1002,错误信息:the params is error
[Yugong series] February 2022 U3D full stack class 007 - production and setting skybox resources
Analysis of using jsonp cross domain vulnerability and XSS vulnerability in honeypot
Greenplum 6.x version change record common manual
IP地址的类别
Data type - floating point (C language)
Greenplum6.x搭建_环境配置
Data type - integer (C language)
MySQL introduction - crud Foundation (establishment of the prototype of the idea of adding, deleting, changing and searching)
Category of IP address
随机推荐
Data analysis methodology and previous experience summary 2 [notes dry goods]
leetcode135. Distribute candy
Compilation and linking of programs
opencv之图像分割
2 - 3 arbre de recherche
Analysis of using jsonp cross domain vulnerability and XSS vulnerability in honeypot
About using CDN based on Kangle and EP panel
2-3查找樹
What is the method of manual wiring in PCB design in 22protel DXP_ Chengdu electromechanical Development Undertaking
数据库存储---表分区
Composer change domestic image
Other 7 features of TCP [sliding window mechanism ▲]
MySQL introduction - crud Foundation (establishment of the prototype of the idea of adding, deleting, changing and searching)
iptables 之 state模块(ftp服务练习)
Required String parameter ‘XXX‘ is not present
Opencv converts 16 bit image data to 8 bits and 8 to 16
Componentspace2022, assertions, protocols, bindings, and configuration files
Download and install orcale database11.2.0.4
[paper reading] icml2020: can autonomous vehicles identify, recover from, and adapt to distribution shifts?
关于基于kangle和EP面板使用CDN