[luoguP3052] [USACO12MAR]摩天大楼里的奶牛Cows in a Skyscraper（DP）

传送门

输出被阉割了。

只输出最少分的组数即可。

f 数组为结构体

f[S]nt 表示集合 S 最少的分组数

f[S].v　 表示集合 S 最少分组数下当前组所用的最少容量

f[S] = min(f[S], f[S i] + a[i]) (i ∈ S)

运算重载一下即可。

——代码

1 #include <cstdio> 2 #include <iostream> 3 4 int n, m, w; 5 int a[19]; 6 struct qwq 7 10 }f[1 << 19]; 11 12 inline qwq operator + (const qwq x, const int d) 13 16 17 inline bool operator < (const qwq x, const qwq y) 18 21 22 inline qwq min(qwq x, qwq y) 23 26 27 inline int read() 28 35 36 int main() 37 51 } 52 printf("%d\n", f[m]nt + 1); 53 return 0; 54 }
View Code

上一篇：[luoguP2858] [USACO06FEB]奶牛零食Treats for the Cows（DP）

下一篇：[luoguP2875] [USACO07FEB]牛的词汇The Cow Lexicon（DP）

---

DP