长沙网站制作公司,网络培训课堂app,有关网站建设的图片,phyton 网站开发Problem - D - Codeforces
题目大意#xff1a;有一个n个数的数组a#xff0c;数m初始为0#xff0c;每次操作可以删除任意一个数#xff0c;然后m加上那个数#xff0c;求n次操作和m的最小值
1n5000#xff1b;0a[i]1e9
思路#xff1a;可以发现有一个n个数的数组a数m初始为0每次操作可以删除任意一个数然后m加上那个数求n次操作和m的最小值
1n50000a[i]1e9
思路可以发现如果我们要删除某个数那么一定要把所有和这个数相等的数全部删去这样才能使MEX变小同时所有大于MEX的数删去的花费都是0所以我们每次操作的数的大小都是递减的且只会操作MEX到0。
那么我们令dp[i]等于MEX等于i时的最小花费我们从MEX到0枚举i同时枚举该删哪个数也就是从0到i-1遍历当前最小花费就是不删这个数dp[j]或者删这个数也就是dp[i]当前MEX*这个数数量-1再加这个数转移方程为dp[j]min(dp[j],dp[i]i*(cnt[j]-1)j)
//#include__msvc_all_public_headers.hpp
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N 5e3 5;
ll n;
ll a[N];
ll cost[N];
ll cnt[N];
void init()
{for (int i 0; i n; i){cost[i] 1e18;cnt[i] 0;}
}
ll gcd(ll a, ll b)
{return b ? gcd(b, a % b) : a;
}
ll lowbit(ll x)
{return x (-x);
}
void solve()
{ll m;cin n;init();for (int i 1; i n; i){cin a[i];if (a[i] n){//MEX最大为n大于n的都可以随便删cnt[a[i]];}}int mex 0;while (cnt[mex]){//找当前的MEXmex;}cost[mex] 0;for (ll i mex; i 0; i--){for (ll j 0; j i; j){cost[j] min(cost[j], cost[i] i * (cnt[j] - 1) j);}}cout cost[0] endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin t;while (t--){solve();}return 0;
}
