url: https://www.luogu.com.cn/problem/P1156

tag:
动态规划，排序，背包DP

思路：
对于每一个垃圾来说，为了不去处理时间，可以按照时间顺序排列，之后只要关注两个属性，一个是高度，一个是时间。定义 f 数组，表示当前高度下生存的时间。每次更新先是判断当前高度能否等到这个垃圾，然后判断如果堆起来能不能逃出去，能的话输出这个垃圾掉落的时间。不能的话计算堆上去时的高度的 f ，用max更新，因为有可能不同的垃圾堆出相同的高度，这个时候需要保留最大值，然后再更新如果吃了之后当前高度的生存时间。最后假如不能出逃，就输出 f[0] 表示当高度为0时的生存时间，也就是最长的生存时间。

代码：

#include <iostream>  
#include <cstdio>  
#include <algorithm>  
#include <cstring>  
using namespace std;  
const int N = 110;  
struct rb {  
    int t, h, w;  
    bool operator < (const rb &b)const  
    {  
        return t < b.t;  
    }  
}r[N];  
  
int d, n;  
int f[N];  
int main()  
{  
    cin >> d >> n;  
    for (int i = 1; i <= n; i ++)  
    {  
        cin >> r[i].t >> r[i].w >> r[i].h;  
    }  
    sort(r + 1, r + n + 1);  
    f[0] = 10;  
    for (int i = 1; i <= n; i ++)  
        for (int j = d; j >= 0; j --)  
        {  
            if (f[j] >= r[i].t)  
            {  
                if (j + r[i].h >= d)  
                {  
                    cout << r[i].t << endl;  
                    return 0;  
                }  
                f[j + r[i].h] = max(f[j], f[j + r[i].h]);  
                f[j] += r[i].w;  
            }  
        }  
    cout << f[0];  
    return 0;  
}

url: https://www.luogu.com.cn/problem/P2966

tag:
USACO09DEC，最短路，排序，USACO，2009

思路：
多次询问，点的数据范围小，所以可以用floyd，如果没有点权，那么这道题就是经典的多源汇最短路。为了处理这个点权，我们可以将每一个节点按照点权的大小从小到大排序，然后对于每一个中间节点都是按照从小到大来遍历，这样计算点权的时候，每次中间节点k一定是最大的，所以求点权的最大值时，只要在i，j，k也就是起点终点和用来更新的中间节点之间选择一个较大的即可。

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 300;
int n, m, q;
int ans[N][N], dist[N][N];
struct node {
    int val, idx;
} Node[N];
bool cmp (node &a, node &b)
{
    return a.val < b.val;
}
int main()
{
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i ++)
    {
        cin >> Node[i].val;
        Node[i].idx = i;
    }
    sort(Node + 1, Node + n + 1, cmp);
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            dist[i][j] = (i == j) ? 0 : 0x3f3f3f3f;
    memset(ans, 0x3f, sizeof ans);
    for (int i = 1; i <= m;  i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = dist[v][u] = min(dist[v][u], w);
    }
    for (int k = 1; k <= n; k ++)
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
            {
                dist[Node[i].idx][Node[j].idx] = min(dist[Node[i].idx][Node[j].idx], dist[Node[i].idx][Node[k].idx] + dist[Node[k].idx][Node[j].idx]);
                ans[Node[i].idx][Node[j].idx] = min(ans[Node[i].idx][Node[j].idx], dist[Node[i].idx][Node[j].idx] + max({Node[i].val, Node[j].val, Node[k].val}));
            }
    while (q --)
    {
        int a, b;
        cin >> a >> b;
        cout << ans[a][b] << endl;
    }
    return 0;
}