9 solutions
-
4
动态规划
顺推
- 推演过程：
- 13 ====>13
- 11 8 ====>24 21
- 12 7 26 ====>36 31 47
- 6 14 15 8 ====>42 50 62 55
- 12 7 13 24 11 ====>54 57 75 86 66
完整代码
#include<bits/stdc++.h> #define ll long long using namespace std; ll n,num[1005][1005]; ll cnt[1005][1005],ans; int main() { std::ios::sync_with_stdio(false); memset(num,0,sizeof(num));//本题使用动态规划 memset(cnt,0,sizeof(cnt));//顺推 cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) cin>>num[i][j]; cnt[1][1]=num[1][1]; for(int i=2;i<=n;i++)//状态转化 for(int j=1;j<=i;j++) cnt[i][j]=num[i][j]+max(cnt[i-1][j-1],cnt[i-1][j]); for(int i=1;i<=n;i++){//找最大 if(ans<cnt[n][i]) ans=cnt[n][i]; } cout<<ans; return 0; }逆推
- 推演过程：
- 13 ====>86
- 11 8 ====>57 73
- 12 7 26 ====>39 46 65
- 6 14 15 8 ====>18 27 39 32
- 12 7 13 24 11 ====>12 7 13 24 11
for(int i=1;i<=n;i++) cnt[n][i]=num[n][i]; for(int i=n-1;i>=1;i--){ for(int j=1;j<=i;j++) cnt[i]][j]=num[i][j]+max(cnt[i-1][j-1],cnt[i-1][j]); } cout<<cnt[1][1];//cnt[1][1]为最大在逆推的基础上可以用一维数组进行空间优化
- 推演过程:
- 86 73 65 32 11
- 57 73 65 32 11
- 39 46 65 32 11
- 18 27 39 32 11
- 12 7 13 24 11
#include<bits/stdc++.h> #define ll long long using namespace std; ll n,num[1005][1005]; ll cnt[1005],ans; int main() { std::ios::sync_with_stdio(false); memset(num,0,sizeof(num)); memset(cnt,0,sizeof(cnt)); cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) cin>>num[i][j]; for(int i=1;i<=n;i++)//先将最后一组数据赋给cnt cnt[i]=num[n][i]; for(int i=n-1;i>=1;i--) for(int j=1;j<=i;j++) cnt[j]=num[i][j]+max(cnt[j],cnt[j+1]); cout<<cnt[1]; return 0; } - 推演过程：
-
1
我相信不少人，第一反应 肯定是 DFS 吧，所以 在这里 把 DFS 和 DP 的代码 都奉上。当然 单纯的 DFS 是过不了的。会超时！
#include <iostream> #include <algorithm> using namespace std; int maxSum = 0; int sum = 0; int arr[1005][1005]; bool vis[1005][1005]; int R; int off[2][2] = { {1,0},{1,1} }; int dp[1005][1005]; void dfs11(int x,int y) { if (vis[x][y]) { return; } else { vis[x][y] = true; sum += arr[x][y]; } if (x == R) {// 已经走到了 最底部 if (maxSum < sum) { maxSum = sum; } return; } for (int i = 0; i < 2; ++i) { int tempX = x + off[i][0]; int tempY = y + off[i][1]; if (tempY > tempX) { continue; } dfs11(tempX, tempY); vis[tempX][tempY] = false; sum -= arr[tempX][tempY]; } } int main(void) { cin >> R; for (int i = 1; i <= R; ++i) { for (int j = 1; j <= i; ++j) { cin >> arr[i][j]; } } //dfs11(1, 1);// 从 第一行 第一列 开始 走 //dp[i][j] = dp[i-1][j] for (int i = 1; i <= R; ++i) { for (int j = 1; j <= i; ++j) { if (j == 0) { dp[i][j] = dp[i - 1][j] + arr[i][j];// 只有一种选择 } else if (j == i) { dp[i][j] = dp[i - 1][j - 1] + arr[i][j]; // 只有一种选择 } else { dp[i][j] = max(dp[i - 1][j - 1], dp[i-1][j]) + arr[i][j]; } } } for (int i = 1; i <= R; ++i) { maxSum = max(maxSum, dp[R][i]); } cout << maxSum << endl; return 0; } -
0
#include <bits/stdc++.h> #define endl '\n' using namespace std; typedef pair<int, int> PII; using ll = long long; using ULL = unsigned long long; const int N = 1e7 + 5; int n,a[1010][1010]; inline void solve() { cin >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) cin >> a[i][j]; for (int i = n - 1; i >= 1; i--) { for (int j = 1; j <= i; j++) { a[i][j] = max(a[i][j]+a[i+1][j],a[i][j]+a[i+1][j+1]); } } cout << a[1][1] << endl; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _ = 1; //int _; cin >> _; while (_--) solve(); return 0; } -
0
#include<iostream> #include<cmath> #include<algorithm> #include<queue> using namespace std; using ll = long long; const int N = 1e3+10; ll a[N][N],sum; int main() { ll sum = 0; int r;cin>>r; for(int i = 1;i <= r;i++) { for(int j = 1;j <= i;j++) { cin>>a[i][j]; } } for(int i = 2;i <= r;i++) { for(int j = 1;j <= i;j++) { //一定要注意考虑边界值 if(j == 1) { a[i][j] += a[i-1][j]; } else if(j == i) { a[i][j] += a[i-1][j-1]; } else { a[i][j] += max(a[i-1][j],a[i-1][j-1]); } } } for(int j = 1; j <= r;j++) { sum = max(sum,a[r][j]); } cout<<sum<<"\n"; return 0; } -
0
#include <bits/stdc++.h> using namespace std; int ma[1010][1010]; int sum[1010][1010]; int main() { int r; cin>>r; for(int i=1;i<=r;i++) { for(int j=1;j<=i;j++) cin>>ma[i][j]; } for(int i=1;i<=r;i++) { for(int j=1;j<=i;j++) { sum[i][j]=ma[i][j]+max(sum[i-1][j],sum[i-1][j-1]); } } cout<<*max_element(sum[r]+1,sum[r]+1+r); } -
0
DFS 记忆化搜索
#include <bits/stdc++.h> using namespace std; #define DBG(x) cout << #x << "=" << x << endl const int N = 1005; int n, a[N][N], f[N][N]; int dfs(int x, int y) { // 查缓存，记忆化 if (f[x][y] != -1) return f[x][y]; // 边界：最后一行 if (x == n) return f[x][y] = a[x][y]; // 记忆化搜索 return f[x][y] = max(dfs(x + 1,y), dfs(x + 1, y + 1)) + a[x][y]; } void solve() { scanf("%d", &n); for(int i = 1; i <= n; i++) for(int j = 1; j <= i; j++) scanf("%d", &a[i][j]); memset(f, -1, sizeof f); dfs(1, 1); printf("%d\n", f[1][1]); } int main() { solve(); return 0; } -
0
动态规划，来看我的。
#include<bits/stdc++.h> using namespace std; typedef long long LL; //dp[i][j]//i:高度，j：位置 /* dp[i][j] = max(dp[i+1][j],dp[i+1][j]) + w[i][j] */ const int N = 1e3+10; int w[N][N]; //每个点的权值 LL dp[N][N]; //存储每个点及以下的权值和 int main(){ int R; cin>>R; for(int i=1;i<=R;i++){ int j=i; for(int j=1;j<=i;j++){ int c; cin>>c; w[i][j] = c; } } for(int i=R;i>=1;i--){ for(int j=1;j<=i;j++){ if(i==R){ dp[i][j]=w[i][j]; } else{ dp[i][j] = max(dp[i+1][j],dp[i+1][j+1]) + w[i][j]; } } } cout<<dp[1][1]<<endl; return 0; } -
0
emm....雀食是个动态规划的模板题，直接上代码吧
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> using namespace std; int num[1005][1005]; int main(void) { int n; cin>>n; for(int i=1;i<=n;i++) for(int k=1;k<=i;k++) cin>>num[i][k];//输入 for(int i=1;i<=n;i++) for(int k=1;k<=i;k++) num[i][k]=max(num[i][k]+num[i-1][k],num[i][k]+num[i-1][k-1]);//想象成把数层层往下加，一直加到最后一层 int ans=0; for(int i=1;i<=n;i++) ans=max(ans,num[n][i]);//比较最后一层哪个最大输出即可 cout<<ans; return 0; }
- 1