当前位置:网站首页>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
边栏推荐
- Speaking of a software entrepreneurship project, is there anyone willing to invest?
- [Yugong series] February 2022 U3D full stack class 005 unity engine view
- Other 7 features of TCP [sliding window mechanism ▲]
- Redis fault handling "can't save in background: fork: cannot allocate memory“
- 快速集成认证服务-HarmonyOS平台
- Three usage scenarios of annotation @configurationproperties
- [Chongqing Guangdong education] accounting reference materials of Nanjing University of Information Engineering
- Novice entry SCM must understand those things
- Frequently Asked Coding Problems
- Redis summary
猜你喜欢
Download and install orcale database11.2.0.4
Pointer advanced, string function
Calling the creation engine interface of Huawei game multimedia service returns error code 1002, error message: the params is error
最长上升子序列模型 AcWing 1017. 怪盗基德的滑翔翼
Greenplum6.x常用语句
Platformization, a fulcrum of strong chain complementing chain
Analysis of using jsonp cross domain vulnerability and XSS vulnerability in honeypot
JS operation
登山小分队(dfs)
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
随机推荐
channel. Detailed explanation of queuedeclare parameters
Required String parameter ‘XXX‘ is not present
JS的操作
selenium自动化集成,八年测试经验软测工程师,一篇文章带你学懂
Find the original code, inverse code and complement of signed numbers [C language]
Gson转换实体类为json时报declares multiple JSON fields named
Redis summary
数据分片介绍
Speaking of a software entrepreneurship project, is there anyone willing to invest?
Greenplum 6.x build_ Environment configuration
[Yugong series] February 2022 U3D full stack class 006 unity toolbar
更改当前文件夹及文件夹下文件日期shell脚本
Selenium automation integration, eight years of testing experience, soft test engineer, an article to teach you
A bug using module project in idea
[Chongqing Guangdong education] organic electronics (Bilingual) reference materials of Nanjing University of Posts and Telecommunications
Greenplum 6.x reinitialization
What are the advantages of commas in conditional statements- What is the advantage of commas in a conditional statement?
Tips for using jeditabletable
PPT模板、素材下载网站(纯干货,建议收藏)
Opencv converts 16 bit image data to 8 bits and 8 to 16