526互联

The 2nd Universal Cup. Stage 4: Taipei - I(状压DP)

发布时间 2023-10-08 16:43:43作者: Qiansui

目录

I. Interval Addition

题意
给定一个长度为 n $(1\le n \le 23) $ 的数组 a。你可以进行一种操作：选择区间 \([l, r]\) 并给这个区间所有的数都加上一个任意的数。问你使得整个数组均为 0 所需的最小操作次数？

思路
考虑差分数组
无论怎么对于区间 \([l, r]\) 进行操作，\(b_l + b_{r + 1}\) 的值保持不变

代码

//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
//#define int long long

using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*

*/
const int N = 25 + 5, M = 1 << 23 | 3, inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
int n, a[N], b[N], ans, dp[M];
ll sum[M];

void solve(){
	cin >> n;
	for(int i = 1; i <= n; ++ i) cin >> a[i];
	for(int i = 0; i < n; ++ i) b[i] = a[i + 1] - a[i];
	for(int i = 1, ed = (1 << n) - 1; i <= ed; ++ i){
		for(int j = 0; j < n; ++ j){
			if(i >> j & 1){
				sum[i] = sum[i - (1 << j)] + b[j];
				break;
			}
		}
	}
	dp[0] = -1;
	for(int i = 0, ed = (1 << n) - 1; i <= ed; ++ i){
		if(sum[i] == 0) ++ dp[i];
		for(int j = 0; j < n; ++ j){
			if((i >> j & 1) == 0){
				dp[i | 1 << j] = max(dp[i | 1 << j], dp[i]);
			}
		}
		ans = max(ans, dp[i]);
	}
	cout << n - ans << '\n';
	return ;
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int _ = 1;
	// cin >> _;
	while(_ --){
		solve();
	}
	return 0;
}