,
从 \(a_1\dots a_n\) , \(b_1\dots b_n\) 中各选出 \(K\) 个数 , 且至少 \(L\) 组下标在两个数组中都被选择 , 使选出的数总和最大
多组数据 , \(T ≤ 10 , 1 ≤∑n ≤ 10^6 , 1 ≤ L ≤ K ≤ n ≤ 2 × 10^5 , 1 ≤ a_i , b_i ≤ 10^9\)考场上写的是 \(O(n^4)\) 的 \(DP\) , 设 \(dp[i][j][k][l]\) 为到第 \(i\) 位 , 一共选了 \(j\) 对 , 其中 \(a\) 选了 \(k\) 个 , \(b\) 选了 \(l\) 个的方案数 . 可以过 \(n<=30\) , \(28\)分 . 再往上开内存就不够了 , 直接编译不了 .
#include#include #include #include #define debug(...) fprintf(stderr,__VA_ARGS__)#define Debug(x) cout<<#x<<"="< < 57){if(c=='-')f=-1;c=getchar();} while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar(); return f*x;}const int N = 31;int a[N], b[N], c[N], d[N], e[N];int n, K, L, T;/*namespace tanxin{ LL ans = 0; inline bool cmp1(int x, int y){ return a[x] + b[x] > a[y] + b[y]; } inline int solve(){ ans = 0; for(int i = 1; i <= n; ++i) c[i] = i; sort(c + 1, c + n + 1, cmp1); for(int i = 1; i <= L; ++i) ans += a[c[i]] + b[c[i]]; for(int i = L + 1; i <= n; ++i) d[i - L] = a[c[i]], e[i - L] = b[c[i]]; sort(d + 1, d + L + 1); sort(e + 1, e + L + 1); for(int i = 1; i <= K - L; ++i) ans += d[i] + e[i]; printf("%lld\n", ans); }};*/namespace baoli_1{ LL dp[N][N][N][N]; LL ans; inline void chkmax(LL& a, LL b){ if(b > a) a = b; } inline void main(){ memset(dp, -1, sizeof dp); dp[0][0][0][0]=0; ans = 0; for(int i = 0; i <= n - 1; ++i) for(int j = 0; j <= K; ++j) for(int k = 0; k <= K; ++k) for(int l = 0; l <= K; ++l) if(~dp[i][j][k][l]){ chkmax(dp[i+1][j][k][l], dp[i][j][k][l]); if(j < K && k < K && l < K) chkmax(dp[i+1][j+1][k+1][l+1], dp[i][j][k][l] + a[i+1] + b[i+1]); if(k < K) chkmax(dp[i+1][j][k+1][l], dp[i][j][k][l] + a[i+1]); if(l < K) chkmax(dp[i+1][j][k][l+1], dp[i][j][k][l] + b[i+1]); } for(int i = L; i <= K; ++i) chkmax(ans, dp[n][i][K][K]); printf("%lld\n", ans); }};int main(){#ifndef file freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout);#endif T = read(); while(T--){ n = read(), K = read(), L = read(); for(int i = 1; i <= n; ++i) a[i] = read(); for(int i = 1; i <= n; ++i) b[i] = read(); //tanxin::solve(); if(n <= 150) baoli_1::main(); }}
然后我又到 \(LOJ\) 上找了一个.
总体思路是先选出 \(K-L\) 组下标不同的 , 再选出 \(L\) 组下标相同的 .先选出 \(K-L\) 组下标不同的 , 就直接在 \(a\) 和 \(b\) 中选出最大的 \(K-L\) 个 , 再选出剩下 \(L\) 对
如果第一阶段选出了下标相同的 , 就记下选了 \(cnt\) 对 , 第二阶段中有 \(cnt\) 次可以不选相同的 , 这样就能保证至少选了 \(L\) 组相同的 . 此时也就是没有限制 , 直接选出 \(a\) 和 \(b\) 中最大的即可 .再选出 \(L\) 对 , 有三种选法 : 选出 \(a+b\) 最大的 ; 已经选了 \(a\) 中的 \(b\) 最大的 + \(a\) 最大的 ; 已经选了 \(b\) 中的 \(a\) 最大的 + \(b\) 最大的 . 要用几个堆维护这些下标 , 还要记录每个下标被选的状态 , 并及时更新 . 对于没取满的状态要及时放入该放的堆里 , 对于取满的状态如果是第一阶段要更新 \(cnt\) .
由于要用堆维护"贪心"的下标 , 时间复杂度是 \(O(n\log n)\) , \(n\) 为 \(\sum n = 10^6\) .
本题难点已经加粗 , 具体细节见代码#include#include #include #include #include #define debug(...) fprintf(stderr,__VA_ARGS__)#define Debug(x) cout<<#x<<"="< < 57){if(c=='-')f=-1;c=getchar();} while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar(); return f*x;}const int N = 1e6 + 5;int a[N], b[N], op[N];bool visa[N], visb[N];int T, n, K, L, cnt;struct Rank_a{ inline bool operator()(int& x, int& y){return a[x] < a[y];} };struct Rank_b{ inline bool operator()(int& x, int& y){return b[x] < b[y];} };struct Rank_ab{ inline bool operator()(int& x, int& y){return a[x]+b[x] < a[y]+b[y];} };priority_queue