题解

95 条题解

  • 2
    @ 2019-08-03 17:22:59

    背包九讲里面的K大背包问题,每次维护一个长度为K的队列,求K优解时只要将两个队列进行归并即可。

    复杂度 O(nmk)

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define INF 0x3f3f3f3f
     
    /* --- Quick I/O --- */
     
    template<class T> inline T Max(const T &x, const T &y){
        return x>y?x:y;
    }
    
    template<class T> inline T Min(const T &x, const T &y){
        return x<y?x:y;
    }
    
    inline ll read(){
        ll s=0,w=1; char ch=getchar();
        while (ch<'0'||ch>'9') {if (ch=='-') w=-1; ch=getchar();}
        while (ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^'0'), ch=getchar();
        return s*w;
    }
     
    void write(ll s){
        if (s<0) s=-s,putchar('-');
        if (s>9) write(s/10);
        putchar(s%10+'0');
    }
     
    void writeln(ll s){
        write(s); putchar('\n');
    }
     
    void writeln(){
        putchar('\n');
    }
    
    int n,v,k;
    
    ll f[5012][55],w[233],c[233],tmp[55*2];
    
    int main(){
        ios::sync_with_stdio(false);
        k = read(); v = read(); n = read();
        memset(f,-0x3f,sizeof(f)); f[0][1] = 0;
        for (int i=1;i<=n;i++) w[i] = read(), c[i] = read();
        for (int i=1;i<=n;i++){
            for (int j=v;j>=w[i];j--){
                int p=1,q=1;
                for (int o=1;o<=k;o++){
                    if (f[j][p]>f[j-w[i]][q]+c[i]) tmp[o] = f[j][p++]; else tmp[o] = f[j-w[i]][q++]+c[i];
                }
                for (int o=1;o<=k;o++) f[j][o] = tmp[o];
            }
        }
        ll ans = 0;
        for (int i=1;i<=k;i++) ans += f[v][i];
        writeln(ans);
        return 0;
    }
    
  • 1
    @ 2017-09-25 16:55:57

    最开始我想到的是DFS的做法,可惜复杂度实在是太高了。 (搜索O(2^N), DPO(KVN))
    之后还是看网上的解法,发现这道题居然是经典的 "K大背包" 问题。问题立即被简单解决,而它与普通背包的区别,也只是体现在了状态和转移上。

    状态:F[ i ][ j ](表示装了i的体积下,第j优的情况)

    转移:F[ i ][ 1 ] = max(F[ i ][ 1 ] , F[ i - W[ p ] ][ 1 ] + V[ p ] ) (特别情况)
    F[ i ][ x ] 的转移来自 F[ i ][ y ] 或 F[ i - W[ p ] ][ z ] + V[ p ]

    由于易知:
    1. F[ i ][ h ] >= F[ i ][ h+1 ]
    2. F[ i - W[ p ] ][ h ] + V[ p ] >= F[ i - W[ p ] ][ h+1 ] + V[ p ]
    我们就可以分别维护 F[ i ][ y ] 和 F[ i - W[ p ] ][ z ] + V[ p ] 两种情况的转移值
    用queue即可轻松实现 (类似归并排序的比较)

    DFS:(过前两点)

    #include <map>
    #include <cmath>
    #include <ctime>
    #include <queue>
    #include <stack>
    #include <cstdio>
    #include <vector>
    #include <bitset>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #define LL long long
    #define INF (0x3f3f3f3f)
    #define LINF (0x3f3f3f3f3f3f3f3fLL)
    using namespace std;
    const int Nsize=205;
    struct GOOD 
    {
        int v,w;    
        bool operator < (const GOOD &x) const 
        {
            return v>x.v;   
        }
    };
    int K,V,N;
    GOOD G[Nsize];
    priority_queue<int> Q;
    void DFS (int f,int v,int s) 
    {
        
        if (v==V) Q.push(s);
        if (f>N||v>=V) return;
        DFS(f+1,v+G[f].w,s+G[f].v);
        DFS(f+1,v,s);
        
    }
    int main () 
    {
        cin>>K>>V>>N;
        for(int i=1;i<=N;i++) cin>>G[i].w>>G[i].v;
        sort(G+1,G+N+1);
        DFS(1,0,0);
        int ans=0;
        for(int i=1;i<=K;i++) 
        {
            ans+=Q.top();   
            Q.pop();
        }
        cout<<ans;
        return 0;
    }
    

    DP:

    #include <map>
    #include <cmath>
    #include <ctime>
    #include <queue>
    #include <stack>
    #include <cstdio>
    #include <vector>
    #include <bitset>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #define LL long long
    #define INF (0x3f3f3f3f)
    #define LINF (0x3f3f3f3f3f3f3f3fLL)
    using namespace std;
    const int Ksize=55;
    const int Nsize=205;
    const int Msize=5005;
    int K,M,N;
    int W[Nsize],V[Nsize],F[Msize][Ksize];
    queue<int> Q1,Q2;
    int main () 
    {
        cin>>K>>M>>N;
        for(int i=1;i<=N;i++) cin>>W[i]>>V[i];
        memset(F,-INF,sizeof(F));
        F[0][1]=0;
        for(int i=1;i<=N;i++) 
            for(int j=M;j>=W[i];j--) 
            {
                for(int o=1;o<=K;o++) 
                {
                    Q1.push(F[j][o]);
                    Q2.push(F[j-W[i]][o]+V[i]); 
                }       
                for(int o=1;o<=K;o++) 
                    if (Q1.front()>Q2.front()) 
                    {
                        F[j][o]=Q1.front();
                        Q1.pop();       
                    }
                    else
                    {
                        F[j][o]=Q2.front();
                        Q2.pop();                   
                    }
                while(!Q1.empty()) Q1.pop();
                while(!Q2.empty()) Q2.pop();
            }
        int ans=0;
        for(int i=1;i<=K;i++) ans+=F[M][i];
        cout<<ans;  
        return 0;
    }
    
  • 1
    @ 2017-04-09 18:51:31
    //p1412
    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    int k,v,n,w[201],p[201];
    vector<int> f[5001];
    
    int main()
    {
        int i,j,sum;
        cin>>k>>v>>n;
        for (i=1;i<=n;i++) cin>>w[i]>>p[i];
        f[0].push_back(0);
        push_heap(f[0].begin(),f[0].end(),greater<int>());
        for (i=1;i<=n;i++)
            for (j=v;j>=w[i];j--)
                for (int kk=0;kk<f[j-w[i]].size();kk++)
                {    
                    if (f[j].size()<k)
                    { 
                        f[j].push_back(f[j-w[i]][kk]+p[i]);
                        push_heap(f[j].begin(),f[j].end(),greater<int>());
                    }
                    else {
                        if (f[j-w[i]][kk]+p[i]>f[j].front())
                        {
                            pop_heap(f[j].begin(),f[j].end(),greater<int>());
                            f[j].pop_back();
                            f[j].push_back(f[j-w[i]][kk]+p[i]);
                            push_heap(f[j].begin(),f[j].end(),greater<int>());                   
                        }
                    }
                }
        sum=0;
        for (i=0;i<f[v].size();i++) sum+=f[v][i];
        cout<<sum<<endl;
        return 0;       
    }
    
    
  • 0
    @ 2017-08-23 14:20:36

    //一个简洁的归并代码
    //不解释qwq
    #include<bits/stdc++.h>
    using namespace std;

    int c[205], p[205], f[5005][55];

    int main()
    {
    memset(f, 0x8f, sizeof(f));
    int k, v, n;
    cin>>k>>v>>n;
    for(int i=1;i<=n;i++) scanf("%d%d", &c[i], &p[i]);
    f[0][1]=0;
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    for(int j=v;j>=c[i];j--){
    int arr[55], iter=1, a=1, b=1;
    memset(arr, 0x8f, sizeof(arr));
    while(iter<=k){
    if(a>f[j][0]&&b>f[j-c[i]][0]) //两数组都用完了
    break;
    if(a>f[j][0]||(b<=f[j-c[i]][0]&&f[j][a]<f[j-c[i]][b]+p[i]))//分类讨论
    arr[iter]=f[j-c[i]][b++]+p[i];
    else
    arr[iter]=f[j][a++];
    iter++;
    }
    for(int l=1;l<iter;l++) f[j][l]=arr[l];
    f[j][0]=iter-1;
    }

    int ans=0;
    for(int i=1;i<=k;i++)
    ans+=f[v][i];
    cout<<ans<<endl;

    return 0;
    }

  • 0
    @ 2017-04-17 10:44:19

    注意到题目所求的是前k大的方案,直接在DP时归并即可。可以使用std::inplace_merge()

    #include <bits/stdc++.h>
    using namespace std;
    int dp[5001][101];
    const int INF=0x3f3f3f3f;
    int main(){
        int k,v,n;
        scanf("%d%d%d",&k,&v,&n);
        for(int i=0;i<=v;i++)
            for(int j=1;j<=k;j++)
                dp[i][j]=-INF;
        dp[0][1]=0;
        while(n--){
            int x,y;
            scanf("%d%d",&x,&y);
            for(int i=v;i>=x;i--){
                for(int j=1;j<=k;j++)
                    dp[i][j+k]=dp[i-x][j]+y;
                inplace_merge(dp[i]+1,dp[i]+k+1,dp[i]+2*k+1,greater<int>());
            }
        }
        int ans=0;
        for(int i=1;i<=k;i++)
            ans+=dp[v][i];
        printf("%d",ans);
    }
    
  • 0
    @ 2016-11-27 18:16:08

    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 4716 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 4716 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 4716 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 4716 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 4716 KiB, score = 10
    测试数据 #5: Accepted, time = 46 ms, mem = 4716 KiB, score = 20
    测试数据 #6: Accepted, time = 78 ms, mem = 4716 KiB, score = 30
    Accepted, time = 184 ms, mem = 4716 KiB, score = 100

    终于过了,因为这道题才去看了背包九讲和归并排序。这道题一开始一直没想到的就是那个【每个背包必须填满】的条件,看了看题解发现可以把dp数组赋值负数代表无法填满,这样一来只要dp数组对应的值是正数那么这个结果就一定是正确的了。。。。

    #include<iostream>
    #include<cstring>
    #include<vector>
    #include<sstream>
    #include<algorithm>
    #include<string>
    #include<cstdio>
    #include<math.h>
    #include<cctype>
    #include<vector>
    #define maxn 5005
    using namespace std;
    int K, V, N;
    int dp[maxn][210], v[maxn], p[maxn], a[210], b[210];
    int main()
    {
        cin >> K >> V >> N;
        for (int i = 1; i <= N; i += 1)
            cin >> v[i] >> p[i];
        for (int i = 0; i <= V; i++)
            for (int j = 1; j <= K; j++)
                dp[i][j] = -maxn;
        dp[0][1] = 0;
        a[K + 1] = b[K + 1] = -1;
        for (int i = 1; i <=N; i += 1){
            for (int j = V; j >= v[i]; j -= 1)
            {
                if (dp[j - v[i]][1] > -1){
                    for (int k = 1; k <= K; k += 1){
                        a[k] = dp[j][k];
                        b[k] = dp[j - v[i]][k] + p[i];
                    }
                    int cur = 1, ca = 1, cb = 1;
                    while (cur <= K && (a[ca] != -1 || a[cb] != -1)){
                        if (a[ca] > b[cb]){
                            dp[j][cur] = a[ca]; ca += 1;
                        }
                        else{
                            dp[j][cur] = b[cb]; cb += 1;
                        }
                        /*if (dp[j][cur] != dp[j][cur - 1])*/ //仍然想不通为什么不能判重
                        cur += 1;
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= K; i += 1)
            ans += dp[V][i];
        cout << ans << endl;
        /*system("pause");*/
        return 0;
    }
    
  • 0
  • 0
    @ 2016-10-30 20:30:52
    type
        re=record
            v,w:longint;
        end;
    
    var
        n,m,z,i,j,k:longint;
        ans:int64;
        a:array[0..200]of re;
        g1,g2:array[0..50]of int64;
        f:array[0..5000,0..50]of int64;
    
    function max(x,y:int64):int64;
    begin
        if x>y then exit(x) else
            exit(y);
    end;
    
    procedure Init;
    var
        i:longint;
    begin
        readln(z,m,n);
        for i:=1 to n do read(a[i].w,a[i].v);
    end;
    
    procedure merger(w:longint);
    var
        i,j,tot:longint;
    begin
        for i:=1 to z do g2[i]:=f[w][i];
        i:=1; j:=1; tot:=0;
        while tot<=z do
        begin
            inc(tot);
            if g1[i]>g2[j] then
            begin
                f[w][tot]:=g1[i];
                inc(i);
            end else
            begin
                f[w][tot]:=g2[j];
                inc(j);
            end;
        end;
    end;
    
    procedure Main;
    var
        i,j,k:longint;
    begin
        for j:=1 to m do
            for k:=1 to z do f[j][k]:=-(1<<62);
        for i:=1 to n do
            for j:=m downto a[i].w do
            begin
                for k:=1 to z do g1[k]:=-(1<<62);
                for k:=1 to z do
                begin
                    g1[k]:=f[j-a[i].w][k]+a[i].v;
                    if j-a[i].w=0 then break;
                end;
                merger(j);
            end;
    end;
    
    procedure print;
    var
        i:longint;
    begin
        for i:=1 to z do ans:=ans+max(0,f[m][i]);
        writeln(ans);
    end;
    
    begin
        Init;
        Main;
        Print;
    end.
    
  • 0
    @ 2016-10-25 09:34:15
    #include<cstdio>
    #include<iostream>
    using namespace std;
    
    const int maxK=50+5,maxV=5000+5,maxN=200+5,INF=0x7F7F7F7F;
    int K,V,N,q1,q2,a1,a2;
    int f[maxV][maxK],T[maxK];
    void merge(int*,int*,int);
    
    int main()
    {
        int v,a,ans=0;
        scanf("%d %d %d",&K,&V,&N);
        for(int i=0;i<=V;i++)
            for(int j=1;j<=K;j++)
                f[i][j]=-INF;
        f[0][1]=0;
        for(int i=1;i<=N;i++)
        {
            scanf("%d %d",&v,&a);
            for(int j=V;j>=v;j--) if(f[j-v][1]>-1) merge(f[j],f[j-v],a);
        }
        for(int i=1;i<=K;i++) ans+=f[V][i];
        printf("%d\n",ans);
        
        return 0;
    }
    
    void merge(int* A,int* B,int C)
    {
        q1=1,q2=1;
        for(int i=1;i<=K;i++)
        {
            a1=A[q1],a2=B[q2]+C;
            if(a1<a2) T[i]=a2,q2++;
            else T[i]=a1,q1++;
        }
        for(int i=1;i<=K;i++) A[i]=T[i];
    }
    

    01背包+多路归并

  • 0
    @ 2016-07-31 22:25:44

    这...必须纪念一下!
    感谢**Vijos**;
    感谢**zengzhen1002**;
    感谢**DD_engi**;
    Vijos AC126~
    测试数据 #0: Accepted, time = 0 ms, mem = 1824 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 1824 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 1824 KiB, score = 10
    测试数据 #3: Accepted, time = 46 ms, mem = 1828 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 1820 KiB, score = 10
    测试数据 #5: Accepted, time = 156 ms, mem = 1824 KiB, score = 20
    测试数据 #6: Accepted, time = 203 ms, mem = 1824 KiB, score = 30
    Accepted, time = 420 ms, mem = 1828 KiB, score = 100
    # <Pascal Code>
    pascal
    type int=longint;
    var
    k,v,n,i,j,l,ans,x1,x2:int;
    a,b:array[0..201]of int;
    f:array[0..5001,0..51]of int;
    q1,q2:array[0..101]of int;
    begin
    readln(k,v,n);
    for i:=1 to n do readln(a[i],b[i]);
    for i:=0 to 5001 do
    for j:=0 to 51 do f[i,j]:=-maxlongint div 2;
    f[0,1]:=0;
    for i:=1 to n do
    for j:=v downto a[i] do
    if f[j-a[i],1]>-1 then
    begin
    fillchar(q1,sizeof(q1),0);
    fillchar(q2,sizeof(q2),0);
    x1:=1; x2:=1;
    for l:=1 to k do
    begin
    q1[l]:=f[j-a[i],l]+b[i];
    q2[l]:=f[j,l];
    if q1[x1]>=q2[x2] then
    begin
    f[j,l]:=q1[x1];
    inc(x1);
    end else
    begin
    f[j,l]:=q2[x2];
    inc(x2);
    end;
    end;
    end;
    ans:=0;
    for i:=1 to k do ans:=ans+f[i];
    writeln(ans);
    end.

    如果奇迹有颜色,那么一定是**橙色!**

  • 0
    @ 2016-02-01 22:33:22

    要归并哈~

  • 0
    @ 2015-11-15 12:06:33

    本题其实是求01背包的前k优解之和,归并一下就好
    f[i][j] 表示容量为 i 时第 j 优解的值
    关于题目中所述的“背包必须装满”可以这样处理:把数组全部赋 -INF,特殊的是 f[0][0] = 0,这样一来最后
    f[capacity][1..k] 中的负数取值就意味着无法装满。具体见代码。

    #include <stdio.h>
    #include <limits.h>

    int values[300];
    int costs[300];
    int f[5001][51];

    void merge(int to, int from, int value, int size){
    int tmp[105];
    int i = 0, j = 0, k = 0;
    while(i < size && j < size){
    if(f[to][i] > f[from][j]+value)
    tmp[k++] = f[to][i++];
    else
    tmp[k++] = f[from][j++]+value;
    }
    while(i < size)
    tmp[k++] = f[to][i++];
    while(j < size)
    tmp[k++] = f[from][j++]+value;
    for(i=0; i<size; i++)
    f[to][i] = tmp[i];
    }
    int main(){
    int numPack, numThing, capacity;
    int i, j;
    scanf("%d %d %d", &numPack, &capacity, &numThing);
    for(i=0; i<numThing; i++)
    scanf("%d %d", &costs[i], &values[i]);
    for(i=0; i<=capacity; i++){
    for(j=0; j<=numPack; j++)
    f[i][j] = LONG_MIN;
    }
    f[0][0] = 0;
    for(i=0; i<numThing; i++){
    for(j=capacity; j>=costs[i]; j--)
    merge(j, j-costs[i], values[i], numPack);
    }
    j = 0;
    for(i=0; i<numPack && f[capacity][i]>=0; i++)
    j += f[capacity][i];
    printf("%d\n", j);
    return 0;
    }

  • 0
    @ 2015-11-07 00:15:14

    评测结果
    编译成功

    Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
    Copyright (c) 1993-2014 by Florian Klaempfl and others
    Target OS: Win32 for i386
    Compiling foo.pas
    foo.pas(1,5) Note: Local variable "m" not used
    Linking foo.exe
    47 lines compiled, 0.1 sec , 28624 bytes code, 1628 bytes data
    1 note(s) issued
    测试数据 #0: Accepted, time = 0 ms, mem = 1580 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 1576 KiB, score = 10
    测试数据 #2: Accepted, time = 2 ms, mem = 1576 KiB, score = 10
    测试数据 #3: Accepted, time = 93 ms, mem = 1572 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 1572 KiB, score = 10
    测试数据 #5: Accepted, time = 265 ms, mem = 1576 KiB, score = 20
    测试数据 #6: Accepted, time = 218 ms, mem = 1572 KiB, score = 30
    Accepted, time = 593 ms, mem = 1580 KiB, score = 100

  • 0
    @ 2014-08-06 08:50:03

    program p1412;
    var
    w,c:array[1..200] of longint;
    opt:array[0..50,0..5000] of longint;
    n,v,k:longint;
    procedure init;
    var
    i:longint;
    begin
    fillchar(opt,sizeof(opt),0);
    readln(k,v,n);
    for i:=1 to n do
    read(w[i],c[i]);
    opt[0,0]:=1;
    end;
    procedure solve;
    var
    i,j,e,t,temp,s,x:longint;
    begin
    for i:=1 to n do
    for j:=v downto w[i] do
    begin
    for s:=1 to opt[0,j-w[i]] do
    begin
    if opt[0,j]+1<=k then opt[0,j]:=opt[0,j]+1;
    if opt[s,j-w[i]]+c[i]>opt[opt[0,j],j] then
    begin
    opt[opt[0,j],j]:=opt[s,j-w[i]]+c[i];
    x:=opt[0,j]-1;
    for e:=x downto 1 do
    if opt[e,j]<opt[e+1,j] then
    begin
    temp:=opt[e,j];
    opt[e,j]:=opt[e+1,j];
    opt[e+1,j]:=temp;
    end;
    end;
    end;
    end;
    end;
    procedure shuchu;
    var
    i,ans:longint;
    begin
    ans:=0;
    for i:=1 to k do
    ans:=ans+opt[i,v];
    writeln(ans);
    end;
    begin
    init;
    solve;
    shuchu;
    end.

  • 0
    @ 2013-03-11 21:35:24

    如果你是建功的,请记住本题的题解和BUG,(我是过来人)。一开始的我认为都要把到达每个体积的各种价值的解存起来。于是开了一个2维的F[I][J],代表i个体积下,第j个状态下的最优值。最后只要输出inc(s,f[v][i])(i=1 to k);就可以了。后来会爆内存,一个体积下有N多中情况,我记得自己在弄第3个样例时,就有上万。其实只要存K种状态(K个背包)就行。每个体积都枚举K的状态。 下面是方程:
    F[J+A[I]][T]:=F[J][K]+B[I];T和K都会变,把最小的放在K位,然后就可以了。

  • 0
    @ 2010-04-09 12:54:41

    var

    F:Array[0..5000,1..40] of longint; //VIJOS1412

    n,m,v,i,j,k,temp,c,w,p,ans:Longint;

    begin

    readln(n,v,m);

    fillchar(f,sizeof(f),-1);

    f[0][1]:=0;

    for i:=1 to m do

    begin

    read(c,w);

    for j:=v downto c do

    for k:=n downto 1 do

    if f[j-c][k]-1 then

    begin

    temp:=F[j-c][k]+w;

    if temp>F[j][n] then

    begin

    F[j][n]:=temp;

    p:=n;

    while (F[j][p]>F[j][p-1]) and (p>=2) do

    begin

    temp:=F[j][p];

    F[j][p]:=F[j][p-1];

    F[j][p-1]:=temp;

    dec(p)

    end

    end

    end

    end;

    writeln(ans)

    end.

  • 0
    @ 2010-04-07 20:47:43

    STL就是慢...

    #include

    #include

    #include

    #include

    using namespace std;

    bool cmp(int &a,int &b)

    {

    if ( a>b ) return true;

    return false;

    }

    struct heap

    {

    vector data;

    void push(int t)

    {

    data.push_back(t);

    push_heap( data.begin(), data.end(),cmp );

    }

    void pop(void)

    {

    pop_heap( data.begin(), data.end(),cmp );

    data.pop_back();

    }

    int top(void) { return data.front(); }

    int size(void) { return data.size(); }

    };

    #define maxn 201

    #define maxv 5001

    long W[maxn],P[maxn],N,K,V,Ans;

    heap D[maxv];

    int main(void)

    {

    long i,j,k;

    cin>>K>>V>>N;

    for ( i=1;i>W[i]>>P[i];

    D[0].push(0);

    for ( j=1;j-1;i-- )

    if ( i-W[j]>=0 && D[i-W[j]].size() )

    for ( k=0;kD[i].top() )

    {

    D[i].pop();

    D[i].push(x+P[j]);

    }else if ( D[i].size()

  • 0
    @ 2009-11-07 20:19:09

    这题居然诡异到n和v弄反了都能拿到10分…………

    要知道我开始连样例都没过…………

  • 0
    @ 2009-11-06 08:59:35

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 25ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 290ms

    ├ 测试数据 07:答案正确... 384ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:699ms

    一遍AC。。顺便复习了下归并。

  • 0
    @ 2009-11-03 20:04:04

    感谢1S的题解!

    看了我一个多小时,总算明白了。做完以后又发现很水,于是又感叹这一个小时浪费了。。。

信息

ID
1412
难度
6
分类
动态规划 | 背包 点击显示
标签
(无)
递交数
1939
已通过
595
通过率
31%
被复制
2
上传者