04 Jun 2022 872字 3分

今日练习

UVA 10755 有点难！;

P1115;

P1719;

P1115

//
// Created by 21122 on 2022/6/5/0005.
//

#include<iostream>
using namespace std;

const int MAXN = 200005;
int arr[MAXN];
int dp[MAXN];
int res = -1000000000;
int main()
{
    int n;
    cin >>n;
    cin >> arr[1];
    dp[1] = arr[1];
    for(int i = 2; i <= n; i++)
    {
        cin >> arr[i];
        dp[i] = max(arr[i], arr[i] + dp[i - 1]);
        res = max(dp[i], res);
    }
    cout << res;




    return 0;
}

P1719

//
// Created by 21122 on 2022/6/5/0005.
//
#include<iostream>
using namespace std;

const int MAXN = 125;
int arr[MAXN][MAXN];
//int dp[MAXN];
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cin >> arr[i][j];
            // 每行的前缀和
            arr[i][j] += arr[i - 1][j];
        }
    }

    int result = -100000;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= i; j++)
        {   // 从上至下，从左至右进行处理
            int temp = 0;
            int dp[125] = {0};
            for(int k = 1; k <= n; k ++)
            {
                temp = arr[i][k] - arr[i - j][k];
                dp[k] = max(dp[k - 1] + temp, temp);
                result = max(result, dp[k]);
            }

        }
    }

    cout << result << endl;

    return 0;
}