Educational Codeforces Round 165 (Rated for Div. 2) (C、D）

1969C - Minimizing the Sum

题意：

思路：观察到操作数很小，最值问题+操作数很容易想到dp，用 $dp[i][j]$ 表示第 $i$ 个元素，操作了 $j$ 次的最小值总和，转移的时候枚举连续操作了几次即可，而连续操作了几次即将 $a_{i-k} ...a_{i}$ 全部变成其中的最小值。

// Problem: C. Minimizing the Sum
// Contest: Codeforces - Educational Codeforces Round 165 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1969/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define int long long
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{cin >> n >> m;int dp[n + 5][m + 5];memset(dp , 0x3f , sizeof dp);dp[0][0] = 0;for(int i = 1 ; i <= n ; i ++){cin >> a[i];}for(int i = 1 ; i <= n ; i ++){for(int j = 0 ; j <= min(i - 1 , m); j ++){//使用了j次for(int k = 0 ; k <= j ; k ++){//连续使用k次int minn = a[i];for(int t = i ; t >= i - k ; t --)minn = min(a[t] , minn);dp[i][j] = min(dp[i][j] , dp[i - k - 1][j - k] + (k + 1) * minn); }}}
//	cout << dp[4][2] << endl;int ans = llinf;for(int i = 0 ; i <= m ; i++){ans = min(ans , dp[n][i]);}cout << ans << endl;
}            
signed main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

1969D - Shop Game

题意：

思路：

思考Alice可以选择哪些商品：即 $a_{i} <= b_{i}$ 的商品都可以被选择。

思考给定一个商品集合，Bob该如何选择：按照 $b$ 的大小从大到小排列，前 $k$ 个设为免费。

再思考这样一定是最优的么？不一定

若Alice抛弃一个商品，那么他将会少花费 $a_{i}$ 金币，而后Bob会重新按照规则选取k个，因此有可能最终花费的金币数会减少。

思考Alice按照怎么样的顺序抛弃商品：1、原先没有被Bob选中的商品一定不会被Alice抛弃。2、Alice抛弃的是被Bob选中的当中 $a$ 最大的那一个。

因此我们用两个优先队列来维护被Bob选中的那些商品以及没有被Bob选中的商品。

随后我们按照顺序逐个抛弃商品，求整个过程中所赚取金币的最大值即可。

// Problem: D. Shop Game
// Contest: Codeforces - Educational Codeforces Round 165 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1969/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
#define int long long
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
bool cmp(pl a , pl b){if(a.x != b.x){return a.x > b.x;}else{return a.y < b.y;}
}
void solve() 
{cin >> n >> m;vector< pair<int,int> >p(n + 5);for(int i = 0 ; i < n ; i ++)cin >> p[i].y;for(int i = 0 ; i < n ; i ++)cin >> p[i].x;vector< pair<int,int> > ans;LL cost = 0;for(int i = 0 ; i < n ; i ++){if(p[i].y <= p[i].x){ans.pb(p[i]);cost -= p[i].y;}}sort(ans.begin() , ans.end() , cmp);priority_queue<LL> ma;//拿走的for(int i = 0 ; i < min(m , (int)ans.size()) ; i ++){ma.push(ans[i].y);}priority_queue<pl> ma1;//需要购买的		for(int i = m ; i < ans.size() ; i ++){ma1.push({ans[i].x , ans[i].y});cost += ans[i].x;}int maxx = cost; while(!ma.empty() && !ma1.empty()){cost += ma.top();cost -= ma1.top().first;ma.pop();ma.push(ma1.top().second);ma1.pop();maxx = max(maxx , cost);}cout << max(maxx , 0LL) << endl;
}            
signed main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}