【DP】The 15-th Beihang University Collegiate Programming Contest (BCPC 2020) - Final I - Poison AND^OR Affection
2021-05-27 11:32:00 # ACM

题链

做法1 写T了；

这是做法2；

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
#include <bits/stdc++.h>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define PI acos(-1.0)
#define eps 1e-8
#define Pair pair<double,double>
// notice
#define mod 998244353 
#define MAXN 1e18
#define MS 2009

LL n,m;
LL a[MS];
struct node{
	int pos;
	LL val;
};
vector<node > vc[MS];
LL dp[MS][MS]; 

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	for(int i=1;i<=n;i++){
		LL t = -1 ,t1 = a[i] ,t2 = a[i];
		for(int j=i-1;j>=1;j--){
			t1 &= a[j];
			t2 |= a[j];
			LL cc = t1^t2;
			if(cc != t){
				t = cc;
				vc[i].push_back({j,cc});
			}
		}
		vc[i].push_back({1,-1});
	}
	//-- 初始化第 1 层信息 
	LL t1 = a[1], t2 = a[1];
	for(int i=2;i<=n;i++){
		t1 &= a[i];
		t2 |= a[i];
		LL cc = t1^t2;
		dp[1][i] = cc;
	}
	//--  计算每一层 
	for(int i=2;i<=m;i++){
		for(int j=i+1;j<=n;j++){ //-- (j<=i)时 dp[i][j] 都设为 0 
			dp[i][j] = dp[i-1][j-1]; //-- 将第 j 个元素作为单个一组 
			for(int k=0;k<vc[j].size()-1;k++){
				if(vc[j][k].pos <= i-1) break;
				dp[i][j] = max(dp[i][j] ,dp[i-1][vc[j][k].pos-1] + vc[j][k].val);
			}
		}
		
		
	}
	cout << dp[m][n] << "\n";
	

	return 0;
}

Prev
2021-05-27 11:32:00 # ACM
Next