题目

http://www.tyvj.cn/p/1013

描述: 你有m人民币, r人品值, 你现在要追n个妹纸, 每个妹纸需要消耗一定人民币和人品, 还有一定时间, 现在你想泡到最多的妹纸, 输出你需要的最小时间.

题外: 今天龟速 + 龟量

这道题应该在很久很久以前做过, 也不知道AC过没有, 然而今天又做一遍的感受是..

还犯了很多老问题 + 各种手残

讲解一下这个题吧..虽说也不是很难, 然鹅..

题解

法一：正常DP

正常的DP便是f[i][j], 钱为i人品为j时泡到的最多妹纸数量, mi[i][j], 钱为i, 人品为j时泡妹纸的最少所需时间。

转移方程也很好写: f[i][j] = max(f[i][j], f[i - rmb[该妹子]][j - rp[该妹子]] + 1) , 表示泡到最多的妹子

mi[i][j]随着上面的泡不泡该妹子改变, mi[i][j] = min(mi[i][j], mi[i - rmb[该妹子]][j - rp[该妹子]] + time[该妹子]), 表示泡到最多妹子所需要的时间, 且妹子相同时最小的时间

状态一路转移下来就得到答案了.

上代码：

#include <cstdio>
#include <algorithm>
using namespace std;
int rmb[1005], rp[1005], time[1005];
int f[105][105];   
int mi[105][105];
int n, m, r;
int i, v1, v2;
int main(){
	scanf("%d", &n);
	for(i = 1; i <= n; ++i)
		scanf("%d%d%d", &rmb[i], &rp[i], &time[i]);
	scanf("%d%d", &m, &r);

	for(i = 1; i <= n; ++i)
		for(v1 = m; v1 >= 0; --v1)
			for(v2 = r; v2 >= 0; --v2)
				if(v1 >= rmb[i] && v2 >= rp[i])
					if(f[v1][v2] < f[v1 - rmb[i]][v2 - rp[i]] + 1){
						f[v1][v2] = f[v1 - rmb[i]][v2 - rp[i]] + 1;
						mi[v1][v2] = mi[v1 - rmb[i]][v2 - rp[i]] + time[i];
					}else if(f[v1][v2] == f[v1 - rmb[i]][b2 - rp[i]] + 1){
						mi[v1][v2] = min(mi[v1][v2], mi[v1 - rmb[i]][v2 - rp[i]] + time[i]);
					}
	printf("%d", mi[m][r]);
	return 0;
}

法二: dp优化

在FAreStorm博客中的一种方法:

时间越少越好, 所以时间可以看作损失项

妹子越多越好, 妹子可以看做价值value

于是可以把[i][j]得到的妹子最大数f和耗费的时间mi放进一个维度里面, 用这样的一个公式:

收益 = 妹子数 * x - time * y, x,y同时要满足一个妹子的收益 > 泡100个妹子花费时间而造成的损失更高

于是最后f[i][j][k]表示泡了i个妹子, j人品, k人民币, 获得的最大收益!相当于把求解最小时间问题直接转换成了求解最大收益问题, 然后通过收益和时间之间的关系提取出时间就可以了.

f[i][j][k] = max(f[i][j][k], f[i - 1][j][k])

f[i][j + rmb[i]][k + rp[i]] = max(a[i][j + rmb[i]][k + rp[i]], a[i - 1][j][k] + 很大的数 - time[i])

代码如下:

#include <cstdio>
#include <algorithm>
#include <cmath>
#define bb 1000000
using namespace std;
int n, ans;
int rmb[105], rp[105], time[105];
int m, r;
int f[105][205][205];  // 花j元, k人品泡到的最多的妹子数量i的价值
int i, j, k;
int main()
{
    scanf("%d", &n);
    for(i = 1; i <= n; ++i){
        scanf("%d%d%d", &rmb[i], &rp[i], &time[i]);
    }
    scanf("%d%d", &m, &r);

    int maxn = 0;
    for(i = 1; i <= n; ++i)
        for(j = 0; j <= m; ++j)
            for(k = 0; k <= r; ++k){
                f[i][j][k] = max(f[i][j][k], f[i - 1][j][k]);
                f[i][j + rmb[i]][k + rp[i]] = max(f[i][j + rmb[i]][k + rp[i]], f[i - 1][j][k] + bb - time[i]);
                maxn = max(maxn, f[i][j][k]);
            }
    while(maxn > 0)
        maxn -= bb;
    printf("%d", -maxn);
    return 0;
}

题目

题解

法一： 正常DP

法二: dp优化

法一：正常DP