2 条题解

  • 0
    @ 2025-10-8 17:01:00
    #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
      @ 2025-10-8 17:00:47
      #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

      USACO(136)动态规划(位向量型)3:不找零P3092 [USACO13NOV] No Change G

      信息

      ID
      2339
      时间
      1000ms
      内存
      128MiB
      难度
      9
      标签
      递交数
      10
      已通过
      4
      上传者