ACM模版

描述

题解

设 dp[i][j] d p [ i ] [ j ] 表示取第 j j 个数为第 i 个值， i:1∼3，j:0∼n−1 i : 1 ∼ 3 ， j : 0 ∼ n − 1 ，最后输出 min(dp[3][j]) m i n ( d p [ 3 ] [ j ] ) 即可。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 3333;
const long long INF = 0x3f3f3f3f3f3f3f3f;

int n;
int s[MAXN];
int c[MAXN];
long long dp[5][MAXN];

int main(int argc, const char * argv[])
{
#if DEBUG
    freopen("/Users/zyj/Desktop/input.txt", "r", stdin);
    freopen("/Users/zyj/Desktop/output.txt", "w", stdout);
#endif

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", s + i);
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%d", c + i);
    }

    memset(dp, 0x3f, sizeof(dp));
    for (int i = 0; i < n; i++)
    {
        dp[1][i] = c[i];
    }

    for (int i = 2; i <= 3; i++)
    {
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < j; k++)
            {
                if (s[j] > s[k])
                {
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + c[j]);
                }
            }
        }
    }

    long long ans = INF;
    for (int i = 0; i < n; i++)
    {
        if (dp[3][i] < ans)
        {
            ans = dp[3][i];
        }
    }

    if (ans == INF)
    {
        cout << "-1\n";
    }
    else
    {
        cout << ans << '\n';
    }

    return 0;
}