类似最大递增子序列CF９８７Ｃ
It is the middle of 2018 and Maria Stepanovna, who lives outside Krasnokamensk (a town in Zabaikalsky region), wants to rent three displays to highlight an important problem.
There are si<sj<sk should be held.
The rent cost is for the ci. Please determine the smallest cost Maria Stepanovna should pay.
The first line contains a single integer 3≤n≤3000) — the number of displays.
The second line contains 1≤si≤109) — the font sizes on the displays in the order they stand along the road.
The third line contains 1≤ci≤108) — the rent costs for each display.
If there are no three displays that satisfy the criteria, print -1. Otherwise print a single integer — the minimum total rent cost of three displays with indices si<sj<sk.
5
2 4 5 4 10
40 30 20 10 40
90
3
100 101 100
2 4 5
-1
10
1 2 3 4 5 6 7 8 9 10
10 13 11 14 15 12 13 13 18 13
33
In the first example you can, for example, choose displays 40+10+40=90.
In the second example you can't select a valid triple of indices, so the answer is -1.
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 3e3+5;
int a[maxn],b[maxn];
long long dp[maxn][10]; // dp[i][j]表示的是你现在再第i个之后你挑了第j个的时候的最小 值
//dp[i][j] = dp[k][j-1] + a[j];
int main()
{
int n;
scanf("%d",&n);
for(int i = 0 ; i < n ; i++) scanf("%d",&a[i]);
for(int i = 0 ; i < n ; i++) scanf("%d",&b[i]);
memset(dp,inf,sizeof(dp));
for(int i = 0 ; i < n ; i++) dp[i][0] = b[i]; // 初始话一下， 那么第i个数选0本书的时候的最小值为b[i] 0表示的是我已经选了一本书了
for(int k = 0 ; k < 3; k ++)
{
for(int i = 1 ; i < n ; i++)
{
for(int j = 0 ; j < i ; j++)
{
if(a[i] > a[j])
{
dp[i][k] = min(dp[j][k-1]+b[i],dp[i][k]);
}
}
}
}
long long ans = LLONG_MAX;
for(int i = 0 ; i < n ; i++)
{
ans = min(ans,dp[i][2]);
}
if(ans > 3e8) ans = -1;
printf("%d
",ans);
}