generals专题

Miku and Generals-西安邀请赛

题目:https://nanti.jisuanke.com/t/39271 题意:给你n个权值 然你分成两组 使他们的权值和的差最小 ,其中有些点是相互矛盾的,不能分在同一组。 分析:所有点都是100的倍数,可以直接除以100,我们二分图染色,每个联通块只有两种情况,因为确定了一个点的所属集合,相邻点就都确定了,而且只有两个集合,然后dp记录所有组合构成的值,dp[i]表示当前这个差值能不能到