武汉理工大学第四届ACM校赛（B、K）---Day5

本文主要是介绍武汉理工大学第四届ACM校赛（B、K）---Day5，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

B 不降序列

K 雇佣农民

B 不降序列

题意：给定一个不降序列 a ，其序列的权值为 $\sum_{i=1}^{n-1}|a_{i+1} - a_{i}|^{2}$ ,你可以对其进行k次操作，每次操作可以删除或修改 $[a_{2},a_{3}...a_{n-1}]$ 中的一个数字，使其仍然为不降序列。求所能得到的序列权值的最大值

思路：对于任意一个数 $a_{i}$ ，如果要修改使得权值尽可能的大，即要将它变为 $a_{i-1} ora_{i+1}$ 。这种操作下同删除这个数字的结果是一样的，因此我们只需要进行删除操作即可。利用 $dp[i][j]$ 即可，其中i表示了当前数的位置，j表示了当前总共的操作数。对于每次操作，我们删除当前位置之前的一个数。则状态转移方程为 $dp[i][j] = max(dp[i][j] , dp[i - len - 1][j-len] + (a_{i} - a_{i-len -1})^{2})$ 其中len为此时进行的操作数（如果len = 2 则删除前面两个数）

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
const LL maxn = 4e05+7;
const LL N=1000;
const LL mod=1e09+7;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >t;
priority_queue<LL> q;
int cmp(int a,int b)
{return a<b;
}
LL qpow(LL a , LL b)//快速幂
{LL sum=1;while(b){if(b&1){sum=sum*a%mod;}a=a*a%mod;b>>=1;}return sum;
}
LL dp[N][N];
const int INF = -1;
void solve() 
{int n , k ;cin>>n>>k;LL a[n + 5];for(int i = 1 ; i <= n ; i++){cin>>a[i];}for(int i = 0 ; i <= n ; i ++){for(int j = 0; j <= k ; j ++){dp[i][j] = INF;}}dp[1][0] = 0;for(int i = 2 ; i <= n ; i++){for(int j = 0 ; j <= k ; j++)//删除操作{	if(i - j < 2)continue;for(int l = 0 ; l <= j; l ++){LL len = j - l;if(i - len >= 2){dp[i][j] = max(dp[i][j] , dp[i - len - 1][j - len] + (LL)(a[i] - a[i - len - 1]) * (a[i] - a[i - len - 1]));}}}} LL ans = 0;for(int i = 0; i <= k ; i++){ans = max(ans,dp[n][i]);}cout<<ans;
}            
int 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;
}

K 雇佣农民

题意：总共需要n个资源，在第i天的白天可以招募最多i名工人，而在晚上这群工人每个人都会产生1个资源，求出刚好得到n个资源的解决方案，输出字典序最大的方案

思路：首先贪心，假设第 i 天还需要开采 x 个资源，且白天之前的总人数为 m 。若 $m + i \geq x$ 则在白天直接全部招满。否则需要进行分类处理，若 $m \leq x$ ,则只需要在这一天招募 $x - m$ 个工人即可。否则，需要对前面的工人进行“解雇”处理，使得 $i \geq x \geq m$ , 由于所求字典序最大，则要从倒数第二天的工人开始处理。第 j 天的工人对于资源的贡献值 $V$ 为 $i - j + 1$ ,且第 j 天总共有 j 名工人。若 $x + j * V < m$ ，只需要将这一天的招募数量变为0即可。若 $x + j * V >m$ ，同时要求字典序最大，因此我们需要尽可能少解雇工人，则只需要将x变为x能取到的 $x\geq m$ 的最小值即可，然后再进行 $m \leq x$ 时的操作。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
const LL maxn = 4e05+7;
const LL N=1e05+10;
const LL mod=1e09+7;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >t;
priority_queue<LL> q;
int cmp(int a,int b)
{return a<b;
}
LL qpow(LL a , LL b)//快速幂
{LL sum=1;while(b){if(b&1){sum=sum*a%mod;}a=a*a%mod;b>>=1;}return sum;
}
void solve() 
{LL P;LL n;cin>>n;P = n;LL sum = 0;LL idx = 1;vector<LL>ans;ans.pb(0);int f = 0;while(n > 0){if(n >= sum + idx){sum += idx;n -= sum;ans.pb(idx);}else{if(n >= sum){LL k = n - sum;ans.pb(k);n = 0;}else{LL le = sum - n;//			cout<<le<<endl;for(int j = idx - 1 ; j > 0 ; j--){if(le <= 0)break;//共j个人LL v = idx - j + 1;if(le >= v * j){le -= v*j;ans[j] = 0;}else{LL num = le/v;le -= num * v;if(le == 0){ans[j] = j - num;}else{le -= v;ans[j] = j - num - 1;int ab = -le;for(int k = j + 1 ; k < idx ; k ++){if(ab <= 0)break;int num = ab/(idx - k + 1);ans[k] += num;ab -= num*(idx - k + 1);}le = -ab;}}}if(le <= 0){ans.pb(-le);f = 1;}n = 0;}}if(n == 0)f = 1;idx++;}if(f){cout<<ans.size() - 1 <<endl;for(int i = 1 ; i < ans.size() ; i ++){cout<<ans[i]<<" ";}}else{cout<<-1;}
}            
int 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;
}

这篇关于武汉理工大学第四届ACM校赛（B、K）---Day5的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！