526互联

数字三角形模型

发布时间 2023-11-19 09:34:12作者: 可爱的卤蛋

1数字三角形

#include <bits/stdc++.h>
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
typedef long long LL;
const int N = 105, M = N, mod = 1e9 + 7;
using namespace std;
int f[N][N], a[N][N];
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            cin >> a[i][j];

    f[1][1] = a[1][1];

    for(int i = 2; i<= n; i++)
        for(int j = 1; j <= i; j ++)
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];

    int ans = -1;
    for(int i = 1; i <= n; i ++)
        ans = max(ans, f[n][i]);

    cout << ans;
    return 0;
}

数字三角形3

#include <bits/stdc++.h>
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
typedef long long LL;
const int N = 105, M = N, mod = 1e9 + 7;
using namespace std;
int f[N][N], a[N][N];
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            cin >> a[i][j];

    f[1][1] = a[1][1];

    for(int i = 2; i <= n / 2; i ++)
        for(int j = 1; j <= i; j ++)
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];

    for(int i = 1; i < n / 2; i ++) f[n / 2][i] = -0x3f3f3f3f;

    for(int i = n / 2 + 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];

    int ans = -1;
    for(int i = 1; i <= n; i ++)
        ans = max(ans, f[n][i]);

    cout << ans;
    return 0;
}

数字三角形4

#include <bits/stdc++.h>
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
typedef long long LL;
const int N = 105, M = N, mod = 1e9 + 7;
using namespace std;
int f[N][N], a[N][N];
int main()
{
    int n, x, y;
    cin >> n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            cin >> a[i][j];
    cin >> x >> y;

    f[1][1] = a[1][1];

    for(int i = 2; i <= x; i ++)
        for(int j = 1; j <= i; j ++)
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];

    for(int i = 1; i <= x; i ++)
        if(i != y)
            f[x][i] = -0x3f3f3f3f;

    for(int i = x + 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];

    int ans = -1;
    for(int i = 1; i <= n; i ++)
        ans = max(ans, f[n][i]);

    cout << ans;
    return 0;
}

数字三角形2

#include <bits/stdc++.h>
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
typedef long long LL;
const int N = 105, M = N, mod = 100;
using namespace std;
int f[N][N][100], a[N][N];
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            cin >> a[i][j];

    f[1][1][a[1][1] % mod] = 1;

    for(int i = 1; i < n; i++)
        for(int j = 1; j <= i; j ++)
            for(int k = 0; k < mod; k ++){
                if(f[i][j][k]){
                    f[i + 1][j][(k + a[i + 1][j]) % mod] = 1;
                    f[i + 1][j + 1][(k + a[i + 1][j + 1]) % mod] = 1;
                }
            }

    int ans = -1;
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j < mod; j ++){
            if(f[n][i][j]) ans = max(ans, j);
        }

    cout << ans;
    return 0;
}

最低通行费

#include <bits/stdc++.h>
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
typedef long long LL;
const int N = 105, M = N, mod = 1e9 + 7;
using namespace std;
int f[N][N], a[N][N];
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            cin >> a[i][j];

    for(int i = 1; i <= n; i ++){
        f[i][1] = f[i - 1][1] + a[i][1];
        f[1][i] = f[1][i - 1] + a[1][i];
    }

    for(int i = 2; i <= n; i++)
        for(int j = 2; j <= n; j ++)
            f[i][j] = min(f[i][j - 1], f[i - 1][j]) + a[i][j];

    cout << f[n][n];
    return 0;
}