[luoguP1282] 多米诺骨牌（DP + 背包）

传送门

将问题转换成分组背包，每一组有上下两个，每一组中必须选则一个，上面的价值为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

上一篇：[luoguP2158] [SDOI2008]仪仗队（数论）

下一篇：[luoguP3203][HNOI2010]BOUNCE 弹飞绵羊（LCT）

---

DP