360编程题题目截图，交流一下思路

第一题应该是动态规划解背包问题，我用的回溯0.3。

第二题一直通过不了，搞的好烦躁

第一题一直90%，最后一题没看懂。。。

第一题是背包问题，动态规划，O(n^2)

第二题，莫队算法，

第一题把时间最多的项目挑出来，最大时间-1求01背包，完了再加上时间最多的项目。

第二题，预处理一下就好了。O(n) 第三题，把每个节点作为根都遍历一边，每次找出每个节点子节点的个数，和每个节点与根的直接儿子的关系。然后就好求了，O(n^2)

背包问题

我想的是用贪心，先选最小的加 ，然后再取最大的加，两种当中取最大，

#include <bits/stdc++.h> using namespace std; int bag(vector<int> &a, int cap){     int n = a.size() - 1;     vector<vector<int> > DP(n+1, vector<int>(cap+1, 0));     for(int i=1; i<=n; ++i){         for(int j=1; j<=cap; ++j){             if(a[i-1] > j){                 DP[i][j] = DP[i-1][j];             }else{                 DP[i][j] = max(DP[i-1][j], DP[i-1][j-a[i-1]]+a[i-1]);             }         }     }     return DP[n][cap]; } int main(){     int n, t;     cin>>n>>t;     vector<int> a(n, 0);     for(int i=0; i<n; ++i){         cin>>a[i];     }     sort(a.begin(), a.end());     int max = a[n-1];     int res = bag(a, t-1);     cout<<max+res<<endl;     return 0; }