AGC 032 D 题解

115 阅读 0 评论 76 点赞

我是靠谱客的博主舒心水杯，这篇文章主要介绍AGC 032 D 题解，现在分享给大家，希望可以做个参考。

主要思路：

将一个位置的 $p_i$ 向左移动到任意 $j$ ,需要花费 $B$
将一个位置的 $p_i$ 向右移动到任意 $j$ ,需要花费 $A$

将每一个位置染上一个颜色。

不动
向左，答案加上 $B$
向右，答案加上 $A$

选出的点要满足一些性质：

不动的点必须从左往右从小往大
向右的点中最小的必须大于在左边没有动的点中最大的 $\Leftrightarrow$ 左边最靠近的没动的点
向左的点中最大的必须小于在右边没有动的点中最小的 $\Leftrightarrow$ 右边最靠近的没动的点

从左往右扫描：
假设当前位置 $i$ 不动，上一个不动的位置为 $j$ , $a_i>a_j$ 。

则考虑位置 $k, (j < k < i)$ 的颜色。

若 $a_k>a_i$ ，则涂上向右的颜色
若 $a_k<a_j$ ，则涂上向左的颜色

这个dp式子就比较显然了

$dp_{i}$ 表示不动的点结尾为i的最小花费。

$dp_{i}=min{dp_{j}+min{cost}},(j<i)$

直接bit上计算每一段区间内值的个数，计算min cost 就行了。

时间复杂度: $(n^2times log(n))$

复制代码

/*
{
######################
#       Author       #
#        Gary        #
#        2020        #
######################
*/
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
const int MAXN=5001;
int n,a[MAXN+20];
LL dp[MAXN+20];
int bit[MAXN+10]={0};
int sum(int i){
	int s=0;
	while(i>0){
		s+=bit[i];
		i-=i&(-i);
	}
	return s;
}
void add(int i,int x=1){
	while(i<=n){
		bit[i]+=x;
		i+=i&(-i);	
	}
}
void clear(){
	memset(bit,0,sizeof(bit));
}
int main(){
	int A,B;
	scanf("%d%d%d",&n,&A,&B);
	rb(i,1,n)
		scanf("%d",&a[i]);
	a[n+1]=1+n;
	n++;
	LL rest=500000000000000ll;
	dp[0]=0ll;
	rb(i,1,n){
		dp[i]=500000000000000ll;
		clear();
		rl(j,i-1,0){
			if(a[j]<a[i]){
				LL min_cost=0;
				min_cost+=1ll*(sum(a[j]))*B;
				min_cost+=1ll*(sum(n)-sum(a[i]))*A;
				min_cost+=1ll*(sum(a[i])-sum(a[j]))*min(A,B);
				check_min(dp[i],dp[j]+min_cost);
			}
			if(a[j])
			add(a[j]);
		}
//		cout<<dp[i]<<endl;
	}
	cout<<dp[n]<<endl;
	return 0;
}
/** 程序框架：
  *
  *
  *
  *
  **/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/*
{
######################
#       Author       #
#        Gary        #
#        2020        #
######################
*/
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
const int MAXN=5001;
int n,a[MAXN+20];
LL dp[MAXN+20];
int bit[MAXN+10]={0};
int sum(int i){
	int s=0;
	while(i>0){
		s+=bit[i];
		i-=i&(-i);
	}
	return s;
}
void add(int i,int x=1){
	while(i<=n){
		bit[i]+=x;
		i+=i&(-i);	
	}
}
void clear(){
	memset(bit,0,sizeof(bit));
}
int main(){
	int A,B;
	scanf("%d%d%d",&n,&A,&B);
	rb(i,1,n)
		scanf("%d",&a[i]);
	a[n+1]=1+n;
	n++;
	LL rest=500000000000000ll;
	dp[0]=0ll;
	rb(i,1,n){
		dp[i]=500000000000000ll;
		clear();
		rl(j,i-1,0){
			if(a[j]<a[i]){
				LL min_cost=0;
				min_cost+=1ll*(sum(a[j]))*B;
				min_cost+=1ll*(sum(n)-sum(a[i]))*A;
				min_cost+=1ll*(sum(a[i])-sum(a[j]))*min(A,B);
				check_min(dp[i],dp[j]+min_cost);
			}
			if(a[j])
			add(a[j]);
		}
//		cout<<dp[i]<<endl;
	}
	cout<<dp[n]<<endl;
	return 0;
}
/** 程序框架：
  *
  *
  *
  *
  **/