目录
I. Interval Addition
题意
给定一个长度为 n $(1\le n \le 23) $ 的数组 a。你可以进行一种操作：选择区间 \([l, r]\) 并给这个区间所有的数都加上一个任意的数。问你使得整个数组均为 0 所需的最小操作次数？
思路
考虑差分数组
无论怎么对于区间 \([l, r]\) 进行操作，\(b_l + b_{r + 1}\) 的值保持不变
对于每个数单独操作，至多 n 次即可达成目标。如果说我们对分段连续的区间进行操作，那么其构成的大区间可以减少一次总的操作次数。
代码
//>>>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;
}