【数字三角形——DP+找规律】

题目

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N][N], f[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];
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            f[i][j] = max(f[i-1][j], f[i-1][j-1]) + a[i][j];
    
    if(n % 2 == 0) cout << max(f[n][n/2], f[n][n/2+1]);
    else cout << f[n][n/2+1];
    
    return 0;
}

拓展：原来的限制对总体方案的，现在改成对每时每刻的方案

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N][N];
int f[N];
int gc(int i)
{
    return ceil((double)i / 2);
}
int gf(int i)
{
    return floor((double)i / 2);
}
int main()
{
    int n;
    cin >> n;
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= i; j++)
            cin >> a[i][j];
    }
    
    for(int i = 1; i <= n; i++)
    {
        int t1 = 1 + gc(i-1), t2 = 1 + gf(i-1);
        if(t1 == t2) f[t1] = max(f[t1], f[t1-1]) + a[i][t1];
        else
        {
            f[t1] = f[t1-1] + a[i][t1];
            f[t2] = f[t2] + a[i][t2];
        }
        
        for(int j = 1; j <= i; j++)
            if(j != t1 && j != t2) 
                f[j] = 0;
    }
    
    int ans = 0;
    for(int i = 1; i <= n; i++)
        ans = max(ans, f[i]);
        
    cout << ans;
}

原文地址：https://blog.csdn.net/m0_73669127/article/details/143812414

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！