每日一题：货币系统 （背包dp）
题意
$n$ 种面额货币，数量无限，问最多保留几种，使得原来可以组成的仍然可以组成。（$t<=20,n<=100,a[i]<=25000$）
solution
由于大的只会被小的组成，所以先排序，对于存在性问题就显然是完全背包了，dp[i] 表示是否能表示出 $i$ 价值，得到状态转移方程：$dp[i]|=dp[i-a[i]]$，对于已经可以表示出来对 $a[i]$，已经可以由小的组成，因此不需要在枚举。
$n$ 种面额货币，数量无限，问最多保留几种，使得原来可以组成的仍然可以组成。（$t<=20,n<=100,a[i]<=25000$）
由于大的只会被小的组成，所以先排序，对于存在性问题就显然是完全背包了，dp[i] 表示是否能表示出 $i$ 价值，得到状态转移方程：$dp[i]|=dp[i-a[i]]$，对于已经可以表示出来对 $a[i]$，已经可以由小的组成，因此不需要在枚举。
n 条木板，每条木板都被分成 m 段且每一段都有要涂的颜色，有 t 次机会涂色，每次可以选择一条木板的连续一段涂成同一种颜色，问最多可以涂对多少段。
考虑四维dp的做法。$dp[i][j][k][0/1]$ 代表到第 $i$ 条第 $j$ 段时涂 $k$ 次，当前段涂红或蓝$(0/1)$的最大正确数，可以得到转移方程：
Update your browser to view this website correctly.&npsb;Update my browser now