当前位置:网站首页>Digital triangle model acwing 1027 Grid access
Digital triangle model acwing 1027 Grid access
2022-07-07 08:51:00 【T_ Y_ F666】
Digital triangle model AcWing 1027. Take the number of squares
Original link
AcWing 1027. Take the number of squares
Algorithm tags
DP linear DP
Ideas
Wrong thinking : Go twice
Since there may be multiple solutions with the first time of travel , You can only choose one of them . But the first place you walk will be reset to 0, It is impossible to determine whether the value of the second time will be greater than the answer you have obtained when the first time is also the optimal solution and is not selected by you
Code
#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;
}
// Sum of row and column values The row determines the column
rep(k, 2, n+n+1){
// First time i That's ok
rep(i1, 1, n+1){
// Second time i That's ok
rep(i2, 1, n+1){
// j1 It means the first time j Column j2 It means the second time j Column
int j1=k-i1, j2=k-i2;
if(j1>=1&&j1<=n&&j2>=1&&j2<=n){
int t=a[i1][j1];
// Not the same path
if(i1-i2){
t+=a[i2][j2];
}
// Next Lower right The lower right Right, right
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;
}
Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support
边栏推荐
- 如何统计项目代码行数
- Greenplum6.x重新初始化
- channel. Detailed explanation of queuedeclare parameters
- redis故障处理 “Can‘t save in background: fork: Cannot allocate memory“
- leetcode135. Distribute candy
- Why choose cloud native database
- [Yugong series] February 2022 U3D full stack class 005 unity engine view
- leetcode134. gas station
- Find the original code, inverse code and complement of signed numbers [C language]
- 调用华为游戏多媒体服务的创建引擎接口返回错误码1002,错误信息:the params is error
猜你喜欢
[Yugong series] February 2022 U3D full stack class 005 unity engine view
ncs成都新電面試經驗
Markdown编辑器Editor.md插件的使用
调用华为游戏多媒体服务的创建引擎接口返回错误码1002,错误信息:the params is error
Teach you how to select PCB board by hand (II)
Data type - integer (C language)
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
MySQL主从延迟的解决方案
Novice entry SCM must understand those things
为不同类型设备构建应用的三大更新 | 2022 I/O 重点回顾
随机推荐
MySQL主从延迟的解决方案
测试人一定要会的技能:selenium的三种等待方式解读,清晰明了
Novice entry SCM must understand those things
AVL balanced binary search tree
mysql分区讲解及操作语句
POJ - 3616 Milking Time(DP+LIS)
Data type - integer (C language)
Mock. JS usage details
leetcode134. gas station
年薪50w阿裏P8親自下場,教你如何從測試進階
9c09730c0eea36d495c3ff6efe3708d8
cmake命令行使用
Explain Huawei's application market in detail, and gradually reduce 32-bit package applications and strategies in 2022
Composer change domestic image
How to add a mask of a target in a picture
Gson转换实体类为json时报declares multiple JSON fields named
指针进阶,字符串函数
Analysis of using jsonp cross domain vulnerability and XSS vulnerability in honeypot
阿里p8手把手教你,自动化测试应该如何实现多线程?赶紧码住
How to realize sliding operation component in fast application