2 条题解
-
0
#include <bits/stdc++.h> using namespace std; const int N = 18, M = 1e5 + 10; typedef long long LL; LL c[N], p[M], s[M], g[(1 << N)], f[(1 << N)]; int m; LL calc(int x, LL last) { int l = last, r = m; while (l <= r) { int mid = (l + r) / 2; if (s[mid] - s[last - 1] == x) return mid; if (s[mid] - s[last - 1] < x) l = mid + 1; else r = mid - 1; } return r; } int main() { int n; scanf("%d%d", &n, &m); LL sum = 0, ans = 1e18; s[0] = 0; for (int i = 1; i <= n; i++) scanf("%lld", &c[i]), sum += c[i]; for (int i = 1; i <= m; i++) scanf("%lld", &p[i]), s[i] = s[i - 1] + p[i]; memset(f, 0, sizeof(f)); memset(g, 0x3f, sizeof(g)); g[0] = 0; for (int i = 1; i < (1 << n); i++) { for (int j = 1; j <= n; j++) if (i & (1 << (j - 1))) { int x = i ^ (1 << (j - 1)); LL d = calc(c[j], f[x] + 1); if (d > f[i]) { f[i] = d; g[i] = g[x] + c[j]; if (f[i] == m) ans = min(g[i], ans); } } } printf("%lld\n", (sum - ans < 0) ? -1 : sum - ans); return 0; } -
0
#include<bits/stdc++.h> using namespace std; const int N=18, M=1e5+10; typedef long long LL; LL c[N], p[M], s[M], g[(1<<N)], f[(1<<N)]; int m; LL calc(int x, LL last){ int l=last, r=m; while(l<=r){ int mid=(l+r)/2; if(s[mid]-s[last-1]==x) return mid; if(s[mid]-s[last-1]<x) l=mid+1; else r=mid-1; } return r; } int main(){ int n; scanf("%d%d", &n, &m); LL sum=0, ans=1e18; s[0]=0; for(int i=1; i<=n; i++) scanf("%lld", &c[i]), sum+=c[i]; for(int i=1; i<=m; i++) scanf("%lld", &p[i]), s[i]=s[i-1]+p[i]; memset(f, 0, sizeof(f)); memset(g, 0x3f, sizeof(g)); g[0]=0; for(int i=1; i<(1<<n); i++){ for(int j=1; j<=n; j++) if(i&(1<<(j-1))){ int x=i^(1<<(j-1)); LL d=calc(c[j], f[x]+1); if(d>f[i]){ f[i]=d; g[i]=g[x]+c[j]; if(f[i]==m) ans=min(g[i], ans); } } } printf("%lld\n", (sum-ans<0)? -1: sum-ans); return 0; }
- 1
信息
- ID
- 2339
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 9
- 标签
- 递交数
- 10
- 已通过
- 4
- 上传者