题解 P1509 【找啊找啊找GF】

· · 题解

次要性动态规划

本篇题解有...

一，什么是次要性dp

次要性dp是指，在使得一个条件到达最优的情况下，让第二个条件也达到最优，在第二个条件也达到最优时，让第三个条件也最优...

这种分先后次序（或者说分主次）依次达成最优解的动态规划，被称为 次要性dp

（定义看看就好了，不懂也没事）

二，怎样做

（参考算法竞赛入门经典解题指南）

确定优化目标

本题的优化目标有两个

1）让xx的女朋友最多

2）让xx在女朋友最多的情况下，花费时间最少

我们可以设xx最后的女朋友数最后为 a ，xx最后花费的时间为t,

则我们可以把最小化目标定为

M * a - t

其中M是一个很大的正整数

你一定会问，为什么要这么干？

你可以想象成一个百分比：

xx的女朋友数对答案的影响为 p%

xx的花费时间对答案的影响为 k%

在这道题目里xx的女朋友个数 对 答案的影响

比xx的花费时间对答案的影响大的多

（或者说起决定性作用）

因此，我们要确保xx的女朋友数对答案的影响的百分比 远大于 xx的花费时间 对答案的影响

事实上，你只需要确保

M > 所有的 xx花费的时间 总和 tmax

这样，当a不同的时候，a对答案起决定性作用，

只有当a相同的时候，t 才会对答案起决定性作用

给出代码：

#include <iostream>
#include <cstdio>
#include <cstring> 
using namespace std;
const int maxn = 150;
int rd(){
    int x = 0, f = 1;char c = getchar();
    while( c < '0' || c > '9' ){if(c == '-'){f = -1;}c = getchar();} 
    while( c <= '9' && c >= '0'){x = x * 10 + c - '0'; c = getchar();}
    return x*f; 
}

int cmax, rpmax;
int N, c[maxn], t[maxn], rp[maxn], f[maxn][maxn];
//f[i][j]表示花费i点money，j点rp，所能得到的最大权值

int w[maxn];//权值被估算后的总权值

int main(){
    N = rd();
    for(int i = 1; i <= N; i++){
        c[i] = rd();
        rp[i] = rd();
        t[i] = rd();        
    }

    for(int i = 1; i <= N; i++){
        w[i] = 20000 - t[i];
    }

    cmax = rd(); rpmax = rd();

    for(int i = 1; i <= N; i++){
        for(int j = cmax; j >= c[i]; j--){
            for(int k = rpmax; k >= rp[i]; k--){
                f[j][k] = max(f[j - c[i]][k - rp[i]] + w[i], f[j][k]);
            }
        }
    }
    cout<<((f[cmax][rpmax]/20000) + 1)*20000 - f[cmax][rpmax];
}

三，优缺点

次要性dp的优缺点是非常明显的：

先来说说优点吧：

代码非常短，非常好写，在处理非常复杂的问题的时候可以大幅度的降低思考时间和出错可能，骗分的不二选择

然后是缺点：

M的值非常难定，而且很容易爆精度，一旦定的太高或者太低，就会爆零，风险很大