1969C - Minimizing the Sum
题意：
思路：观察到操作数很小，最值问题+操作数很容易想到dp，用表示第
个元素，操作了
次的最小值总和，转移的时候枚举连续操作了几次即可，而连续操作了几次即将
全部变成其中的最小值。
// 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可以选择哪些商品：即的商品都可以被选择。
思考给定一个商品集合，Bob该如何选择：按照的大小从大到小排列，前
个设为免费。
再思考这样一定是最优的么？不一定
若Alice抛弃一个商品，那么他将会少花费金币，而后Bob会重新按照规则选取k个，因此有可能最终花费的金币数会减少。
思考Alice按照怎么样的顺序抛弃商品：1、原先没有被Bob选中的商品一定不会被Alice抛弃。2、Alice抛弃的是被Bob选中的当中最大的那一个。
因此我们用两个优先队列来维护被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;
}
