该题题义很明确，看了题之后也会想到这时一个DP题目，问题在于如何来定义状态，以及建立合理的动态规划方程来求解这个问题。
本题的输出是在泡到MM最多的情况下，花最少的时间。因此，时间的权限小于泡到MM的数量，为此我们可以用一个二维背包求解出最多能够泡到多少女生，这个并不难。再往后，如何保证时间是最少的呢，我的做法是再开一个数组，用来记录花费为 i “rmb”，j “rp”的最少时间，将时间数组的更新与二维背包求解最多MM数量做到同时更新，这样便能够保证一定是在泡到MM数量不减少的情况下的最少时间。
代码如下：
#include#include #include #include #define MAXN 105using namespace std;int N, Cash, Rp, rmb[MAXN], rp[MAXN], t[MAXN];int dp[MAXN][MAXN];int tt[MAXN][MAXN];void DP(){ memset(dp, 0, sizeof (dp)); // 记录最多能够泡到多少MM memset(tt, 0, sizeof (tt)); // tt记录相对应的所要开销的时间 for (int i = 1; i <= N; ++i) { for (int j = Cash; j >= rmb[i]; --j) { for (int k = Rp; k >= rp[i]; --k) { if (dp[j][k] < dp[j-rmb[i]][k-rp[i]] + 1) { dp[j][k] = dp[j-rmb[i]][k-rp[i]] + 1; tt[j][k] = tt[j-rmb[i]][k-rp[i]]+t[i]; } else if (dp[j][k] == dp[j-rmb[i]][k-rp[i]] + 1) { tt[j][k] = min(tt[j][k], tt[j-rmb[i]][k-rp[i]]+t[i]); } } } } printf("%d\n", tt[Cash][Rp]);}int main(){ while (scanf("%d", &N) == 1) { for (int i = 1; i <= N; ++i) { scanf("%d %d %d", &rmb[i], &rp[i], &t[i]); } scanf("%d %d", &Cash, &Rp); DP(); } return 0;}