atcoder ABC 184 F 题解

· · 题解

洛谷题目传送门 原题传送门

这题数据范围较大，不能用 dp。于是我们就可以开两个向量把 b、 c。加一个值之后轮流交换，得出所有的可能装到 b 里，把值装到 c 里面，排序，枚举所有可能，打擂台，找到最优解，最后输出。时间复杂度 O(n^2 \times \log(n)), 不会超时。

AC code

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n,t;
    cin >> n >> t;
    int a[n + 1];
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    vector<int> b,c;
    b.push_back(0);
    c.push_back(0);
    \\下标从一开始
    for(int i = 1;i <= n;i++){
        for(int j = b.size();j--;){
            b.push_back(a[i] + b[j]);
        }
        swap(b,c);
    }\\ 每一种b里都有了。
    sort(b.begin(),b.end(),greater<int>());\\按降序排序
    int ans = 0;
    for(auto x : c){
        if(x > t){
            continue;
        }
        x += *lower_bound(b.begin(),b.end(),t-x,greater());\\二分查找
        ans = max(ans,x); \\更新答案
    }
    cout << ans << endl;\\输出
   return 0;
}