hdu6492

链接

题意

        小伙们打算组团去参加。他们一共有 n+m+2k 个人,包括 n+k 个男生,m+k 个女生,其中 k 对男女生为异性情侣,现在他们要找房间住。房间有三种类型,双人间 a 元一间,三人间 b 元一间,这两种只能同性一起住。情侣间能住一对异性情侣,一间 c 元。除了情侣间以外,其他房间都可以不住满。
        求最少花多少钱,能让小伙伴们都有地方住。

题解

        dp[i]代表i个同性要花多少钱才能住下
        dp[i] <-----   dp[i-2]+a  dp[i-3]+b
        然后枚举情侣房间即可