C1. Pokémon Army (easy version)

C1. Pokémon Army (easy version)

// Problem: C1. Pokémon Army (easy version)// Contest: Codeforces - Codeforces Round #672 (Div. 2)// URL: Memory Limit: 256 MB// Time Limit: 2000 ms// 2022-02-25 13:50:20// // Powered by CP Editor (namespace std;#define rep(i,l,r) for(int i=(l);i<=(r);i++)#define per(i,l,r) for(int i=(l);i>=(r);i--)#define ll long long#define pii pair#define mset(s,t) memset(s,t,sizeof(t))#define mcpy(s,t) memcpy(s,t,sizeof(t))#define fi first#define se second#define pb push_back#define all(x) (x).begin(),(x).end()#define SZ(x) ((int)(x).size())#define mp make_pairconst ll mod = 1e9 + 7;inline ll qmi (ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans = ans * a%mod; a = a * a %mod; b >>= 1; } return ans;}inline int read () { int x = 0, f = 0; char ch = getchar(); while (!isdigit(ch)) f |= (ch=='-'),ch= getchar(); while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return f?-x:x;}template void print(T x) { if (x < 0) putchar('-'), x = -x; if (x >= 10) print(x/10); putchar(x % 10 + '0');}inline ll sub (ll a, ll b) { return ((a - b ) %mod + mod) %mod;}inline ll add (ll a, ll b) { return (a + b) %mod;}inline ll inv (ll a) { return qmi(a, mod - 2);}inline int64_t cal (vector a) { int n = a.size(); vector d1(n + 1), d2(n + 1); d1[0] = -static_cast(1e18); d2[0] = 0; for (int i = 0; i < n; i ++) { d1[i + 1] = max (d1[i], d2[i] + a[i]); d2[i + 1] = max (d2[i], d1[i] - a[i]); } return max(d1.back(), d2.back());}void solve() { int n, q; cin >> n >> q; vector a(n); for (int i = 0; i < n ;i ++) { cin >> a[i]; } cout << cal(a) << "\n"; while (q --) { int x, y; cin >> x >> y; x --, y --; swap(a[x], a[y]); cout << cal(a) << "\n"; }}int main () { int t; t =1; cin >> t; while (t --) solve(); return 0;}

static_cast是强制转换类型 这题用d1表示前i个的最大值并且最后一个是加，d2表示前i个最大值。并且最后一个是减 两种情况分类讨论 因为不可能第1个就是减，所以d1[0] = -1e18类似的有d2[0] = 0 注意相互之间的转换，加减相互转移

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。