当前位置:网站首页>Digital triangle model acwing 275 Pass a note
Digital triangle model acwing 275 Pass a note
2022-07-07 08:51:00 【T_ Y_ F666】
Digital triangle model AcWing 275. Pass slip
Original link
Algorithm tags
Dynamic programming linear DP
Ideas
Optimization of row number value range
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];
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();
}
}
// Sum of row and column values The row determines the column
rep(k, 2, n+m+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<=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;
}
Line number value range optimization 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];
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();
}
}
// Sum of row and column values The row determines the column
rep(k, 2, n+m+1){
// First time i That's ok
rep(i1, max(1ll, k-m), min(k, n)+1){
// Second time i That's ok
rep(i2, max(1ll, k-m), min(k, n)+1){
// k-i1 Indicates the number of columns for the first time k-i2 Indicates the number of secondary columns
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;
}
Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support
边栏推荐
- AVL balanced binary search tree
- xray的简单使用
- Pointer advanced, string function
- Golan idea IntelliJ cannot input Chinese characters
- Go write a program that runs within a certain period of time
- All about PDF crack, a complete solution to meet all your PDF needs
- selenium自动化集成,八年测试经验软测工程师,一篇文章带你学懂
- Gson转换实体类为json时报declares multiple JSON fields named
- 为什么要选择云原生数据库
- Frequently Asked Coding Problems
猜你喜欢
Componentspace2022, assertions, protocols, bindings, and configuration files
[Nanjing University] - [software analysis] course learning notes (I) -introduction
Other 7 features of TCP [sliding window mechanism ▲]
Count sort (diagram)
Mountaineering team (DFS)
Analysis of using jsonp cross domain vulnerability and XSS vulnerability in honeypot
Compilation and linking of programs
Quick sorting (detailed illustration of single way, double way, three way)
Routing information protocol rip
【MySQL】数据库进阶之触发器内容详解
随机推荐
Tronapi wave field interface - source code without encryption - can be opened twice - interface document attached - package based on thinkphp5 - detailed guidance of the author - July 6, 2022 - Novice
leetcode135. Distribute candy
LeetCode 715. Range module
AVL balanced binary search tree
Image segmentation in opencv
Go write a program that runs within a certain period of time
ncs成都新电面试经验
GoLand set goproxy
[Yugong series] February 2022 U3D full stack class 008 - build a galaxy scene
[Chongqing Guangdong education] accounting reference materials of Nanjing University of Information Engineering
Basic data types and string types are converted to each other
Frequently Asked Coding Problems
Speaking of a software entrepreneurship project, is there anyone willing to invest?
Greenplum6.x-版本变化记录-常用手册
let const
[MySQL] detailed explanation of trigger content of database advanced
Lenovo hybrid cloud Lenovo xcloud: 4 major product lines +it service portal
[Yu Yue education] C language programming reference of Zhongbei College of Nanjing Normal University
Mock.js用法详解
[Nanjing University] - [software analysis] course learning notes (I) -introduction