CF-987C Three displays 题解

题目大意

给你一个长度为n的整数序列a[1..n].

以及一个长度为n的整数序列b[1..n].

现在,要求你选择三个正整数i,j,k(1<=i< j< k<=n).

使得a[i]< a[j]< a[k]且b[i]+b[j]+b[k]的值最小.

输出满足要求的b[i]+b[j]+b[k]的最小值。

解题思路

刚开始想的是暴力，但是没想到好的方法暴力。

（脑子真不好使。。

可以暴力$n^2$维护每个点大于他的最小值，之后在$n^2$枚举求解即可。

但是发现可以dp写就dp写吧。

这个dp思路好妙啊。

用dp[i] [x]表示x作为选取的第i的数字的最小值。

状态转移方程为$dp[i] [x] = min(dp[i-1] [x]+j,dp[i] [x])$

只需要$n^2$即可。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#define rep(i,a,n) for (ll i=a;i<=n;i++)
#define per(i,a,n) for (ll i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const int INF = 1e9;
int s[3030], c[3030];
int dp[5][3030];

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans *= a;
		a <<= 1, b >>= 1;
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	int n; cin >> n;
	rep(i, 1, n)	cin >> s[i];
	rep(i, 1, n)	cin >> c[i];
	rep(i, 1, 3) {
		rep(j, 1, n)	dp[i][j] = INF;
	}
	rep(i, 1, n) {
		dp[1][i] = c[i];
		rep(j, 2, 3) {
			rep(k, 1, i - 1) {
				if (s[k] < s[i])	dp[j][i] = min(dp[j][i], c[i] + dp[j - 1][k]);
			}
		}
	}
	int ans = INF;
	rep(i, 1, n)	ans = min(ans, dp[3][i]);
	if (ans == INF)	cout << -1 << endl;
	else cout << ans << endl;
	return 0;
}