问题 B: 分院帽 (hat)

时间限制: 2 Sec  内存限制: 128 MB提交 状态

题目描述

在霍格沃兹魔法学校，每年都要举行分院仪式。 分院帽今年不但负责将学生分到格兰芬多，赫奇帕奇，拉文克劳以及斯莱特林四个学院。还要把一部分学生分到新建起的一所学院 —— StandardDeviation学院。 也就是离入学标准还差一点的学院。（因为想来学习魔法的人真的太多了，大约有n人）但即使是这样，也不能招收太多人，准确来说，学校打算招收m人。 可是，这是一所公平的学校，如果一些同分的学生中，只有一些被招收走了，那么学校将会颜面尽失。老师十分不好办。 根据学校的记录，总共有k对人成绩相同，老师必须让录取公平、同时又和预期招收人数相差最少。 大家都去学习魔法了，老师就把任务交给你了。请你求出最优的录取人数。

输入

第一行三个整数n,m,k 接下来k行每行两个整数，a,b表示a,b两人的成绩相同 （n,m,k∈N*，1≤a,b≤n）

输出

一行，表示既不让同学们抗议，又与原来的m尽可能接近的选出学生的数目。(如果有两种方案与m的差的绝对值相等，选较小的一种：)

样例输入 Copy

4 3 2 2 1 3 4

样例输出 Copy

2

提示

提交状态

 

传送门，很好的dp总结

#pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> using namespace std; int vis[20005]; int num[20005]; int fa[20005]; int dp[20005]; int n,m,k; int cnt=0; void init() { for(int i=1;i<=n;i++) { fa[i]=i; } } int findfa(int a) { if(fa[a]==a) return a; else return fa[a]=findfa(fa[a]); } int main() { cin>>n>>m>>k; init(); for(int i=1; i<=k; i++) { int a,b; scanf("%d%d",&a,&b); fa[a]=b;//谁当father都一样 } for(int i=1; i<=n; i++) { fa[i]=findfa(i); } for(int i=1;i<=n;i++) { num[fa[i]]++; } //for(int i=1;i<=n;i++) // printf("%d ",num[i]); for(int i=1;i<=n;i++) { if(num[i]==0) continue; for(int j=n;j>=num[i];j--) { dp[j]=max(dp[j-num[i]]+num[i],dp[j]); } } int ans=0;//dp[m]; for(int i=1;i<=n;i++) { if(fabs(ans-m)>fabs(m-dp[i])) ans=dp[i]; } cout<<ans; return 0; } /************************************************************** Problem: 16127 User: 2019UPC110 Language: C++ Result: 正确 Time:122 ms Memory:2804 kb ****************************************************************/