样例求解
  • 板块CF1286A Garland
  • 楼主kimi0705
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/12/14 21:53
  • 上次更新2023/12/15 11:57:40
查看原帖
样例求解
637788
kimi0705楼主2023/12/14 21:53
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 105;
int n;
int arr[N], sum[N];
int dp[2][N][2]; // 滚动数组
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) dp[0][i][0] = dp[0][i][1] = INT_MAX;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    for (int I = 1; I <= n; I++) {
        int i = I & 1, s = (I - 1) & 1;
        if (arr[I] == 0) {
            dp[i][0][0] = INT_MAX;
            dp[i][0][1] = dp[s][0][1];
            for (int j = 1; j <= n / 2; j++) {
                dp[i][j][1] = min(dp[s][j - 1][0] + 1, dp[s][j][1]);
                dp[i][j][1] = min(dp[s][j - 1][0], dp[s][j][1] + 1);
            }
        } else if (arr[I] % 2 == 0) {
            dp[i][0][0] = INT_MAX;
            dp[i][0][1] = INT_MAX;
            for (int j = 1; j <= n / 2; j++) {
                dp[i][j][1] = INT_MAX;
                dp[i][j][0] = min(dp[s][j - 1][0], dp[s][j][1] + 1);
            }
        } else {
            dp[i][0][0] = INT_MAX;
            dp[i][0][1] = dp[s][0][1];
            for (int j = 1; j <= (n + 1) / 2; j++) {
                dp[i][j][0] = INT_MAX;
                dp[i][j][1] = min(dp[s][j][1], dp[s][j - 1][0] + 1);
            }
        }
    }
    cout << min(dp[n & 1][n / 2][0], dp[n][n / 2][1]);
    return 0;
}
2023/12/14 21:53
加载中...