题解首发

tp题面

前言

作为一个ACGO新蒟蒻,有幸AC掉一道绿题,大喜,遂有此题解
(孩子们我说一石三鸟有没有懂的)

分析

DP部分

这道题如果不考虑输出答案的话,就是一道二维01背包问题.
二维01背包问题本质上仍是一种01背包,只是代价的维度多了一维;放到本题,就是说代价包括重力、阻力这两个维度.
好啊,他升维我也升维.在转移时多加一维,就可以按01背包问题解决了.
于是我们可以写出这样的搜索代码:

#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
int m,v,n;
struct tool{
    int g,f,t;
}a[105];
bool vis[105];
int tmx = -1;
void MS(int id,int sigma_g,int sigma_f,int tnow,int ix){
    bool flag = true;
    for (int i=id;i<=n;i++){
        if (!vis[i] && sigma_g + a[i].g <= m && sigma_f + a[i].f <= v){
            flag = 0;
            vis[i] = true;
            tnow += a[i].t;
            tmx = max(tmx,tnow);
            MS(i,sigma_g + a[i].g,sigma_f + a[i].f,tnow,ix+1);
            tnow -= a[i].t;
            vis[i] = false;
        }
    }
}
int main(){
    scanf("%d%d%d",&m,&v,&n);
    for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i].g,&a[i].f,&a[i].t);
    for (int i=1;i<=n;i++)
        MS(i,a[i].g,a[i].f,a[i].t,1);
    printf("%d\n",tmx);
    return 0;
}

如果不考虑输出方案,且硬性要求字典序最小的条件,我们似乎可以AC样例了;
但是很可惜,这题还要输出方案并且要求字典序最小,而经过本蒟蒻1h的调试后,发现这代码很难输出正确方案(乱搞才有20分),于是便只能放弃.
(所以最终还是回到了For循环的怀抱)
言归正传,定义$f[i][j][k]$为用前$i$个中的物品重$j$阻力$k$的时间最大值
仿照01背包,我们不难写出状态转移方程:
$f[i][j][k] = max(f[i-1][j][k],f[i-1][j-a[i].g][k-a[i].f]+a[i].t);$
同样类比01背包,发现可以滚动数组优化,于是压掉一维,成为:
$f[j][k] = max(f[j-a[i].g][k-a[i].f]+a[i].t,f[j][k])$
然后.就到最恶心的输出方案了.

输出方案

这里我们开个book数组,
$book[i][j][k]:是否在重力为j、 阻力为k的方案中选了第i个物品,book[i][j][k] = 1是选了,等于0是没选$
然后,从最后一个物品开始由最终状态逆推:是否在重力为m、阻力为v的方案中选了第i个物品
如果选了,就令$m$减去对应物品的重力,$v$减去对应物品的阻力.
什么,要求字典序最小?
可以,我们需要将状态转移方程改为这个:
$f[j][k] = f[j-a[i].g][k-a[i].f]+a[i].t \ (if \ f[j][k] <= f[j-a[i].g][k-a[i].f]+a[i].t))$

Code

主体:

scanf("%d%d%d",&m,&v,&n);
    for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i].g,&a[i].f,&a[i].t);
    //二维01背包问题
    for (int i=1;i<=n;i++)
        for (int j=m;j>=a[i].g;--j)
            for (int k=v;k>=a[i].f;--k)
                if (f[j][k] <= f[j-a[i].g][k-a[i].f]+a[i].t)
                    f[j][k] = f[j-a[i].g][k-a[i].f]+a[i].t,book[i][j][k] = 1;
            

输出:

int G = m,F = v;
    vector <int> ans;
    for (int i=n;i;i--)//逆推方案
        if (book[i][G][F]){
            F -= a[i].f,G -= a[i].g;
            ans.push_back(i);
        }
    for (int i=ans.size()-1;i>-1;i--)//第二次逆序后变成正序
        printf("%d ",ans[i]);

时间复杂度与空间复杂度:$O(nmv)$

后记

如果你做对了这题，可以tp到洛谷P1759去,链接：hack传送门