传送门
将问题转换成分组背包，每一组有上下两个，每一组中必须选则一个，上面的价值为0，下面的价值为1，求价值最小
因为要求上下两部分差值最小，只需从背包大小为总数 / 2 时往前枚举，找最小答案即可。
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define N 100001 5 #define min(x, y) ((x) < (y) ? (x) : (y)) 6 #define max(x, y) ((x) > (y) ? (x) : (y)) 7 8 int n, m, tot, ans; 9 int a[N], b[N], f[N]; 10 11 inline int read() 12 19 20 int main() 21 31 f[0] = 0; 32 for(i = 1; i <= n; i++) 33 for(j = m; j >= 0; j) 34 40 for(i = tot >> 1;;i) 41 48 } 49 }View Code
上一篇：[luoguP1029] 最大公约数和最小公倍数问题（数论）
下一篇：[luoguP3146] [USACO16OPEN]248（区间DP）
DP
