【CF1206B】Make Product Equal One

绝地灬酷狼 2023-06-05 08:54 16阅读 0赞

# Description #

给定一个整数序列，每次操作可以将某一个元素的值+1或-1，求最少需要多少次操作可以使得序列每个元素的乘积等于1

# Solution #

一些数的乘积等于1，那么说明序列中一定只含有1或者是-1，而且-1出现的次数必须为偶数

那么我们定义$f\[i\]\[1/0\]$表示前$i$个数，一共有奇数/偶数个-1时的最小操作数是多少

那么我们考虑转移

如果我们让当前的数变为1，那么从阶段i-1转移到i的时候-1个数的奇偶性不变

同理，变为-1就意味着奇偶性改变

那么状态转移方程就很简单了

# Code #

#include <bits/stdc++.h>
    namespace shl {
        typedef long long ll;
        int n, a[100010];
        ll f[100010][3];
        int c[100010][3];
        inline int read() {
            int ret = 0, op = 1;
            char c = getchar();
            while (!isdigit(c)) {
                if (c == '-') op = -1; 
                c = getchar();
            }
            while (isdigit(c)) {
                ret = (ret << 3) + (ret << 1) + c - '0';
                c = getchar();
            }
            return ret * op;
        }
        inline int aabs(int x) {
            return x >= 0 ? x : -x;
        }
        using std :: min;
        int main() {
            n = read();
            for (register int i = 1; i <= n; ++i) a[i] = read();
            for (register int i = 1; i <= n; ++i) {
                c[i][0] = aabs(a[i] + 1);   // change into -1
                c[i][1] = aabs(a[i] - 1);   // change into 1
                // std :: cerr << c[i][0] << " " << c[i][1] << std :: endl;
            }
            f[0][1] = 1ll << 60;
            for (register int i = 1; i <= n; ++i) {
                f[i][0] = min(f[i - 1][0] + c[i][1], f[i - 1][1] + c[i][0]);
                f[i][1] = min(f[i - 1][1] + c[i][1], f[i - 1][0] + c[i][0]);
            }
            printf("%I64d\n", f[n][0]);
            return 0;
        }
    };
    int main() {
        shl :: main();
        return 0;
    }

转载于:https://www.cnblogs.com/shl-blog/p/11391865.html