首页 > 其他分享 >P4121

P4121

时间:2024-04-01 15:22:35浏览次数:20  
标签:const clock int long return P4121 define

二进制枚举每一个数是给它右侧的还是接收它右侧的,贪心的选择整倍数的,时间复杂度 \(\mathcal{O}(2^nn)\)

// Author: xiaruize
#ifndef ONLINE_JUDGE
bool start_of_memory_use;
#endif
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
clock_t start_clock = clock();
#endif
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
    if (a > b)
        return a;
    return b;
}
int min(int a, int b)
{
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 20 + 10;

int n;
int a[N];
int b[N], c[N];
int m;
int res = 0;

void solve()
{
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    cin >> m;
    int ans = INF;
    rep(msk, 0, (1 << n) - 1)
    {
        int tmp = 0;
        memcpy(c, a, sizeof(a));
        rep(i, 1, n - 1)
        {
            // int t = (b[i] + c[i]) / m;
            // b[i] -= max(t * m - c[i], 0);
            // c[i] -= min(t * m, c[i]);
            // tmp += t;
            if (msk & (1 << i - 1))
            {
                int nd = c[i] % m;
                nd = min(nd, a[i]);
                c[i + 1] += nd;
                c[i] -= nd;
            }
            else
            {
                int nd = (m - c[i] % m) % m;
                nd = min(nd, a[i + 1]);
                c[i] += nd;
                c[i + 1] -= nd;
            }
        }
        // rep(i, 1, n) cerr << b[i] + c[i] << ' ';
        // cerr << endl;
        rep(i, 1, n) tmp += (c[i] + m - 1) / m;
        ans = min(ans, tmp);
    }
    cout << ans + res << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
#ifndef ONLINE_JUDGE
    cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
    cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
    return 0;
}

标签:const,clock,int,long,return,P4121,define
From: https://www.cnblogs.com/xiaruize/p/18108511

相关文章