当前位置:网站首页>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
边栏推荐
- 对API接口或H5接口做签名认证
- Routing information protocol rip
- 数据库存储---表分区
- MAC OSX php dyld: Library not loaded: /usr/local/xxxx. dylib
- 测试踩坑 - 当已有接口(或数据库表中)新增字段时,都需要注意哪些测试点?
- NCS Chengdu Xindian interview experience
- cmake命令行使用
- Gson converts the entity class to JSON times declare multiple JSON fields named
- [Chongqing Guangdong education] organic electronics (Bilingual) reference materials of Nanjing University of Posts and Telecommunications
- Oracle makes it clear at one time that a field with multiple separators will be split into multiple rows, and then multiple rows and columns. Multiple separators will be split into multiple rows, and
猜你喜欢
随机推荐
Analysis of using jsonp cross domain vulnerability and XSS vulnerability in honeypot
为什么要选择云原生数据库
Markdown编辑器Editor.md插件的使用
Calling the creation engine interface of Huawei game multimedia service returns error code 1002, error message: the params is error
调用华为游戏多媒体服务的创建引擎接口返回错误码1002,错误信息:the params is error
Greenplum 6.x build_ install
Laravel8 uses passport login and JWT (generate token)
联想混合云Lenovo xCloud:4大产品线+IT服务门户
Greenplum 6.x monitoring software setup
Newly found yii2 excel processing plug-in
Lenovo hybrid cloud Lenovo xcloud: 4 major product lines +it service portal
POJ - 3784 running medium
Mock.js用法详解
What are the advantages of commas in conditional statements- What is the advantage of commas in a conditional statement?
LeetCode 736. Lisp 语法解析
ncs成都新電面試經驗
調用華為遊戲多媒體服務的創建引擎接口返回錯誤碼1002,錯誤信息:the params is error
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
Implement custom memory allocator
Greenplum6.x重新初始化