CF1380D Berserk And Fireball

CF1380D Berserk And Fireball

其實不能算一個構造題，主要難在代碼實現。

考慮每一個區間，對于這個區間選擇一個最優的方法刪除即可。

顯然我們考慮用當前區間最大的數去刪除其他的數，之后再將其刪除即可。

#include <bits/stdc++.h> using namespace std;//#define Fread //#define Getmod#ifdef Fread char buf[1 << 21], *iS, *iT; #define gc() (iS == iT ? (iT = (iS = buf) + fread (buf, 1, 1 << 21, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++) #define getchar gc #endif // Freadtemplate <typename T> void r1(T &x) {x = 0;char c(getchar());int f(1);for(; c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;for(; '0' <= c && c <= '9';c = getchar()) x = (x * 10) + (c ^ 48);x *= f; }template <typename T,typename... Args> inline void r1(T& t, Args&... args) {r1(t); r1(args...); }#ifdef Getmod const int mod = 1e9 + 7; template <int mod> struct typemod {int z;typemod(int a = 0) : z(a) {}inline int inc(int a,int b) const {return a += b - mod, a + ((a >> 31) & mod);}inline int dec(int a,int b) const {return a -= b, a + ((a >> 31) & mod);}inline int mul(int a,int b) const {return 1ll * a * b % mod;}typemod<mod> operator + (const typemod<mod> &x) const {return typemod(inc(z, x.z));}typemod<mod> operator - (const typemod<mod> &x) const {return typemod(dec(z, x.z));}typemod<mod> operator * (const typemod<mod> &x) const {return typemod(mul(z, x.z));}typemod<mod>& operator += (const typemod<mod> &x) {*this = *this + x; return *this;}typemod<mod>& operator -= (const typemod<mod> &x) {*this = *this - x; return *this;}typemod<mod>& operator *= (const typemod<mod> &x) {*this = *this * x; return *this;}int operator == (const typemod<mod> &x) const {return x.z == z;}int operator != (const typemod<mod> &x) const {return x.z != z;} }; typedef typemod<mod> Tm; #endif#define int long long const int maxn = 2e5 + 5; const int maxm = maxn << 1;int n, m, K, X, Y, flag; int a[maxn], b[maxn];int f(int l,int r) {int ln = r - l - 1;if(ln < 0) return 0;int res = (ln % K) * Y + (ln / K) * min(X, Y * K);if(*max_element(a + l + 1, a + r) > max(a[l], a[r])) {if(ln / K == 0) flag = 1;res = res + X - min(Y * K, X);}return res; }signed main() { // freopen("S.in", "r", stdin); // freopen("S.out", "w", stdout);int i, j, k;r1(n, m, X, K, Y);for(i = 1; i <= n; ++ i) r1(a[i]);for(i = 1; i <= m; ++ i) r1(b[i]);int res(0);for(i = 1, k = 1, j = 0; i <= m + 1; j = k, ++ i) {for(; !flag && a[k] != b[i]; ++ k)flag = (k > n) && (b[i]);res += f(j, k);}printf("%lld\n", flag ? -1 : res);return 0; }

總結

以上是生活随笔為你收集整理的CF1380D Berserk And Fireball 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。