ZR#954 分组

分手后的思念是犯贱 2024-04-20 10:32 69阅读 0赞

##  ##

ZR\#954 分组

### 解法： ###

> 设 $ f\[i\]\[a\]\[b\] $ 表示考虑了排序后的前 $ i $ 个人，目前已经有 $ a $ 个组配好了，还有 $ b $ 个组只有组员没有组长的最小代价。转移时，考虑当前的人是作为组长，加入一个已经有组员的组，还是作为组员新建一个组即可。  
> 然后对于有的人重要程度相同的情况，我们需要想办法继续保证组长在组员的后面。则对于重要程度相同的两个人，我们按照他们的志愿排序：先是只能当组员的，然后是都可以的，然后是只能当组长的。  
> 时间复杂度：$ O(nk^2) $ ，可以通过前 3 个子任务。  
> 然后因为如果 $ k \\times 2 > n $ ，一定无解，所以特判一下就好了。

### CODE: ###

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define LL long long #define N 1001000 #define INF 0x3f3f3f3f3f3f3f3fll LL n,k,f[2][1010][1010]; struct Neo { LL w,s,p; }a[N]; inline bool cmp(Neo x,Neo y) { if(x.w != y.w) return x.w < y.w; return x.p < y.p; } int main() { scanf("%lld%lld",&n,&k); for(int i = 1 ; i <= n ; i++) { scanf("%lld%lld%lld",&a[i].w,&a[i].s,&a[i].p); if(a[i].p == 1) a[i].p = 3; else if(a[i].p == 2) a[i].p = 1; else if(a[i].p == 3) a[i].p = 2; } if(2 * k > n) { puts("-1"); return 0; //system("pause"); } sort(a+1,a+n+1,cmp); memset(f,0x3f,sizeof(f)); f[0][0][0] = 0; int now = 1,las = 0; for(int i = 1 ; i <= n ; i++) { for(int j = 0 ; j <= k ; j++) { for(int l = 0 ; j + l <= k ; l++) { f[now][j][l] = f[las][j][l]; if(a[i].p < 3) { if(l >= 1) f[now][j][l] = min(f[now][j][l],f[las][j][l - 1] + a[i].s); } if(a[i].p > 1) { if(j >= 1) f[now][j][l] = min(f[now][j][l],f[las][j - 1][l + 1]+a[i].s); } } } swap(now,las); } if(f[las][k][0] >= INF) { puts("-1"); return 0; } printf("%lld \n",f[las][k][0]); //system("pause"); return 0; }

转载于:https://www.cnblogs.com/Repulser/p/11448937.html

发表评论取消回复

表情：

评论列表（有 0 条评论，69人围观）

还没有评论，来说两句吧...

相关阅读

相关 ZR#997

ZR\997 解法： > 找找规律就出来了，全场最简单的一道题。 CODE： include<iostream> include<cstdi...

怼烎@/ 2024年04月20日 10:34/ 0 赞/ 73 阅读

相关 ZR#998

ZR\998 解法： > 先把所有物品按照拿走的时间从小到大排序，拿走的时间相同就按照放上去的时间从大到小。那么一件物品上方的物品就一定会在它的前面。 ...

柔光的暖阳◎/ 2024年04月20日 10:33/ 0 赞/ 83 阅读

相关 ZR#954 分组

ZR\954 分组解法： > 设 $ f\[i\]\[a\]\[b\] $ 表示考虑了排序后的前 $ i $ 个人，目前已经有 $ a $ 个组配好了，还...

分手后的思念是犯贱/ 2024年04月20日 10:32/ 0 赞/ 70 阅读

相关 ZR#956 集合

ZR\956 集合解法： > 维护一个异或操作的懒标记，并对应的处理插入、删除和异或操作。接下来考虑如何整体加一。 > 考虑一个数字 $ x $ 变为...

待我称王封你为后i/ 2024年04月20日 10:31/ 0 赞/ 63 阅读

相关 ZR#955 折纸

ZR\955 折纸解法: > 可以发现折纸之后被折到上面的部分实际上是没有用的，因为他和下面对应位置一定是一样的，而影响答案的只有每个位置的颜色和最底层的...

悠悠/ 2024年04月20日 10:29/ 0 赞/ 69 阅读

相关 ZR#712

消灭砖块题意： > 很多块砖分布在一个 $ m \\times m $ 的矩阵中，他可以消掉以他为左上角顶点的一个 $ n \\times n $ 的矩阵...

朱雀/ 2024年04月20日 10:24/ 0 赞/ 57 阅读

相关 ZR#710

雷劈数题意： > 现在给出两个整数，求出位于两个整数之间的所有的“雷劈数。解法： > 因为雷劈数特殊的性质，所以在数据范围中的雷劈数实际很少，直...

ゝ一纸荒年。/ 2024年04月20日 10:24/ 0 赞/ 76 阅读

相关 d954(D9546)

恩施到汉口的D954途经站时刻列表有吗？恩施到汉口的D954这趟动车的开车时间12:19，预计到达时间15:49，总预计用时03:30。 ![d954(D9546)\

矫情吗；*/ 2023年09月26日 12:36/ 0 赞/ 42 阅读

相关 mybatis 一级缓存/二级缓存区别[954L]

文章目录 mybatis\_cache系列前言大白话简述什么是一级缓存？大白话简述什么是二级缓存

缺乏、安全感/ 2023年02月14日 13:03/ 0 赞/ 2 阅读

相关 leetcode 954. Array of Doubled Pairs | 954. 二倍数对数组（Java）

题目 [https://leetcode.com/problems/array-of-doubled-pairs/][https_leetcode.com_problem

比眉伴天荒/ 2022年09月04日 07:52/ 0 赞/ 55 阅读