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

目录

B   不降序列 

 K   雇佣农民

B   不降序列 

        题意：给定一个不降序列 a ，其序列的权值为,你可以对其进行k次操作，每次操作可以删除或修改中的一个数字，使其仍然为不降序列。求所能得到的序列权值的最大值

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

#include 
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 pairpl;
priority_queue, greater >t;
priority_queue q;
int cmp(int a,int b)
{return a>=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<>t;while(t--){solve();}return 0;
}

 K   雇佣农民

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

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

#include 
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 pairpl;
priority_queue, greater >t;
priority_queue q;
int cmp(int a,int b)
{return a>=1;}return sum;
}
void solve() 
{LL P;LL n;cin>>n;P = n;LL sum = 0;LL idx = 1;vectorans;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< 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<>t;while(t--){solve();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！