鏈接：https://codeforces.com/problemset/problem/1400/E
來源：Codeforces
??思路：給你一個陣列，現在你可以進行兩種操作，操作1：將一段沒有 0 的區間進行減一的操作，操作2：將 i 位置上的元素歸零，最終問：將這個陣列的全部元素歸零后操作的最少的次數，首先如果我們只使用操作 2，那么一個區間內最多操作 \(r - l + 1\) 次，如果操作 1 和 操作 2 一起使用，我們可以貪心 + 分治的方式來求出操作次數，如果現在是一個區間，那么我們找到區間內最小的值 \(cnt1\)，此時我們進行操作操作 1 的次數就是 \(cnt1\)，當前這個位置的數字就歸零了，此時這個數字左右兩邊還有可能進行重復的操作，那么當前操作的次數就是 cnt1 + 左右兩邊區間可以操作的次數，這個時候我們需要和只進行操作 2 進行比較，判斷那種方式可以得到最小的操作次數，如果在遞回的程序中最后只是剩下一個不為 0 的數字，那么我們進行一次操作 2，
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e3 + 10;
int a[maxn];
int solve(int l, int r) {
if(l > r) return 0;
else if (l == r) {
if(a[l] == 0) return 0;
else return 1;
}
int cnt1 = 1e9 + 10, mid;
for(int i = l; i <= r; ++ i) {
if(a[i] < cnt1) {
cnt1 = a[i];
mid = i;
}
}
for(int i = l; i <= r; ++ i) a[i] -= cnt1;
return min(cnt1 + solve(l, mid - 1) + solve(mid + 1, r), r - l + 1);
}
int main() {
int n; scanf("%d", &n);
for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
int ans = solve(1, n);
printf("%d\n", ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/249.html
標籤：C++
上一篇：例外宣告