题解

40 条题解

  • 3
    @ 2016-09-06 13:56:03

    不是很懂怎么用DP,二分贪心水过。。。
    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 560 KiB, score = 5
    测试数据 #1: Accepted, time = 0 ms, mem = 560 KiB, score = 5
    测试数据 #2: Accepted, time = 0 ms, mem = 560 KiB, score = 5
    测试数据 #3: Accepted, time = 0 ms, mem = 560 KiB, score = 5
    测试数据 #4: Accepted, time = 0 ms, mem = 560 KiB, score = 5
    测试数据 #5: Accepted, time = 0 ms, mem = 564 KiB, score = 15
    测试数据 #6: Accepted, time = 0 ms, mem = 564 KiB, score = 15
    测试数据 #7: Accepted, time = 0 ms, mem = 560 KiB, score = 15
    测试数据 #8: Accepted, time = 0 ms, mem = 556 KiB, score = 15
    测试数据 #9: Accepted, time = 0 ms, mem = 556 KiB, score = 15
    Accepted, time = 15 ms, mem = 564 KiB, score = 100
    ```c++
    #include <iostream>
    #include <cstdio>
    #include <stack>
    using namespace std;

    int n, k;
    int a[1010];
    stack<int> stk;

    inline bool check(int x) {
    int i, cnt = 0, tmp = 0;
    for(i = n-1;i >= 0;i --) {
    tmp += a[i];
    if(tmp > x) {
    i ++;
    tmp = 0;
    cnt ++;
    if(cnt >= k) return false;
    }
    }
    return true;
    }

    inline void printAns(int x) {
    int i, cnt = 0, tmp = 0;
    stk.push(n);
    for(i = n-1;i >= 0;i --) {
    tmp += a[i];
    if(tmp > x) {
    i ++;
    tmp = 0;
    cnt ++;
    stk.push(i+1);
    stk.push(i);
    }
    }
    stk.push(1);
    while(!stk.empty()) {
    printf("%d ", stk.top());
    stk.pop();
    printf("%d\n", stk.top());
    stk.pop();
    }
    }

    int main() {
    int i, l, r, m;
    scanf("%d%d", &n, &k);
    for(i = 0;i < n;i ++) scanf("%d", a + i);
    for(l = 1, r = 0x3f3f3f3f;l < r - 1;) {
    m = (l + r) >> 1;
    if(check(m)) r = m;
    else l = m;
    }
    if(check(l)) printAns(l);
    else printAns(r);
    return 0;
    }
    ```

  • 1
    @ 2019-08-22 17:27:18

    受到大佬启发,用了二分搜索。怎么改也改不对啊,后来才发现输出有问题。
    如果这号人没有任务,那就不需要输出它的那一行。
    样例如下,输入:

    3 3
    1 2 3
    

    输出:

    1 2
    3 3
    

    二分代码:

    #include <iostream>
    
    using namespace std;
    
    typedef struct
    {
        int a,b;
    }pp;
    
    int task[1001];
    int n,m;
    pp vp[1001]={0};
    
    bool check(int x)
    {
        int acc=0;
        int sum=0;
        int i;
        i=1;
        while(i<=n)
        {
            sum+=task[i];
            if(task[i]>x)
            {
                return false;
            }
            if(sum>x)
            {
                sum=0;
                acc++;
                continue;
            }
            i++;
        }
        if(sum!=0)
        {
            acc++;
        }
        if(acc<=m)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    int main()
    {
        cin>>n>>m;
        int i,j,k,l,sum;
        j=0;
        k=0;
        for(i=1;i<=n;i++)
        {
            cin>>task[i];
            j+=task[i];
        }
        i=0;
        while(i<=j)
        {
            k=(i+j)/2;
            if(check(k))
            {
                j=k-1;
            }
            else
            {
                i=k+1;
            }
        }
        if(check(i))
        {
            k=i;
        }
        else
        {
            k=j;
        }
        l=m;
        i=n;
        j=n;
        while(l>0)
        {
            sum=0;
            for(;i>0;i--)
            {
                sum+=task[i];
                if(sum>k)
                {
                    break;
                }
            }
            vp[l].a=i+1;
            vp[l].b=j;
            j=i;
            l--;
        }
        for(i=1;i<=m;i++)
        {
            if(vp[i].a<=vp[i].b)
            {
                cout<<vp[i].a<<' '<<vp[i].b<<endl;
            }
        }
        return 0;
    }
    
  • 1
    @ 2014-10-18 17:32:33

    其实是二分查找加搜索吧,dp什么的时间复杂度不是很高吗?测试数据 #0: Accepted, time = 0 ms, mem = 828 KiB, score = 5

    测试数据 #1: Accepted, time = 7 ms, mem = 828 KiB, score = 5

    测试数据 #2: Accepted, time = 0 ms, mem = 824 KiB, score = 5

    测试数据 #3: Accepted, time = 0 ms, mem = 824 KiB, score = 5

    测试数据 #4: Accepted, time = 0 ms, mem = 832 KiB, score = 5

    测试数据 #5: Accepted, time = 0 ms, mem = 824 KiB, score = 15

    测试数据 #6: Accepted, time = 15 ms, mem = 824 KiB, score = 15

    测试数据 #7: Accepted, time = 0 ms, mem = 828 KiB, score = 15

    测试数据 #8: Accepted, time = 0 ms, mem = 824 KiB, score = 15

    测试数据 #9: Accepted, time = 0 ms, mem = 828 KiB, score = 15

    下面是代码。第一次写二分查找……调试了好久……好多冗余和负责的东西,大家见谅。
    program a01;
    var
    i,m,n,add:longint;
    ans,max,l,r:int64;
    a:array[1..1005] of longint;

    procedure found;
    var
    s,i:longint;
    k:int64;
    begin
    k:=(l+r) div 2;
    s:=0;
    add:=0;
    for i:= n downto 1 do
    begin
    if a[i]>k then begin
    l:=k+1;
    exit;
    end;
    if add+a[i]>k then begin
    s:=s+1;
    add:=a[i];
    if s=m then begin
    l:=k+1;
    exit;
    end
    end
    else add:=add+a[i];
    end;

    if s<m then begin
    if ans>k then ans:=k;
    r:=k;
    end;
    end;

    procedure print(o:longint);
    var
    i,point:longint;
    begin
    if o=1 then begin
    writeln(1,' ',o);
    exit;
    end;
    point:=0;
    add:=a[o];
    for i :=o-1 downto 1 do
    if add+a[i]>ans then begin
    point:=i+1;
    break;
    end
    else add:=add+a[i];
    if (i=1)and(point=0) then begin
    writeln(1,' ',o);
    exit;
    end;
    print(point-1);
    writeln(point,' ',o);
    end;

    begin
    ans:=maxlongint;
    read(n,m);
    for i := 1 to n do
    begin
    read(a[i]);
    max:=max+a[i];
    end;
    l:=1;
    r:=max;
    while r<>l do
    found;
    add:=0;
    print(n);
    end.

  • 1
    @ 2009-08-27 08:43:38

    哪位神牛解释一下

    const maxm=1000;

    var pre,a,ans:array[1..maxm] of longint;

    l,r,mid,m,k,i:longint;

    function ok(lim:longint):boolean;

    var t,i,sum:longint;

    begin

    fillchar(pre,sizeof(pre),0);

    pre[k+1]:=m+1;

    t:=m;

    for i:=k downto 1 do

    begin

    sum:=0;

    while (t>0) and (sum+a[t]1 then exit(false) else

    begin ans:=pre; exit(true); end;

    end;

    begin

    readln(m,k);

    for i:=1 to m do read(a[i]);

    l:=-1;

    r:=maxlongint>>1;

    while r-l>1 do

    begin

    mid:=(r+l)>>1;

    if ok(mid) then r:=mid else l:=mid;

    end;

    for i:=1 to k do

    writeln(ans[i],' ',ans-1);

    end.

  • 0
    @ 2019-06-15 19:47:58

    看到没有c++的dp题解,就过来了
    首先DP方程如何推就不讲了,直接列出:dp[i][j]=min{max(dp[k][j−1],Sum[k+1,i])}(0≤k<i)
    所以输出的时候就暴力输出,按题意要让后面多抄

    #1 Accepted 4ms 7.988 MiB
    #2 Accepted 4ms 7.961 MiB
    #3 Accepted 4ms 8.027 MiB
    #4 Accepted 8ms 8.082 MiB
    #5 Accepted 19ms 8.086 MiB
    #6 Accepted 4ms 8.074 MiB
    #7 Accepted 176ms 8.094 MiB
    #8 Accepted 99ms 8.094 MiB
    #9 Accepted 17ms 8.074 MiB
    #10 Accepted 23ms 8.07 MiB

    #include<map>
    #include<queue>
    #include<cmath>
    #include<cstdio>
    #include<string>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define N 1010
    #define int long long
    #define debug cout<<__LINE__<<" "<<__FUNCTION__<<"\n"
    
    inline int read(){
        int x=0,y=1;
        char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
        return x*y;
    }
    void put(int x){
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar((x%10)+48);
    }
    int a[N],dp[N][N];
    void print(int x,int ans){
        if(!x) return;
        for(int i=x;i>=0;i--) {
            if(a[x]-a[i-1]>ans||i==0) {
                print(i,ans);
                cout<<i+1<<" "<<x;
                break;
            }
        }
        puts("");
    }
    signed main(){
    //  freopen(".in","r",stdin);
    //  freopen(".out","w",stdout);
        int n=read(),m=read();
        memset(dp,122,sizeof(dp));
        dp[0][0]=0;
        for(int i=1;i<=n;i++) a[i]=read()+a[i-1],dp[1][i]=a[i];
        for(int i=2;i<=m;i++){
            for(int j=i;j<=n;j++){
                for(int k=2;k<=j;k++){
                    if(max(dp[i-1][k-1],a[j]-a[k-1])<dp[i][j]){
                        dp[i][j]=max(dp[i-1][k-1],a[j]-a[k-1]);
                    }
                }
            }
        }
    //  for(int i=1;i<=m;i++){
    //      for(int j=1;j<=n;j++){
    //          cout<<dp[i][j]<<" ";
    //      }
    //      cout<<"\n";
    //  }
        print(n,dp[m][n]);
    //  fclose(stdin);
    //  fclose(stdout);
        return 0;
    }
    
  • 0
    @ 2009-08-27 17:25:03

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    1A

    不用什么二分答案 直接DP

    而且很好写很短 ..

    var

    s:array[1..1000]of longint;

    f,t:array[0..1000,0..1000]of longint;

    mm:array[1..10000,1..2]of longint;

    n,m:longint;

    procedure init;

    var

    i,j,total:longint;

    begin

    readln(n,m);

    if n=m then begin

    for i:=1 to n do writeln(i,' ',i);

    halt;

    end;

    for i:=1 to n do read(s[i]);

    for i:=1 to n do begin

    total:=0;

    for j:=i to n do begin

    inc(total,s[j]);

    t:=total;

    end;

    end;

    end;

    function max(x,y:longint):longint;

    begin

    if x>y then exit(x);

    exit(y);

    end;

    function min(x,y:longint):longint;

    begin

    if x>y then exit(y);

    exit(x);

    end;

    procedure main;

    var

    i,j,k,x1,total,ans,r:longint;

    begin

    for i:=0 to n do f[0,i]:=10000000;

    for i:=1 to m do

    for j:=1 to n do begin

    f:=t[1,j];

    for k:=j-1 downto 1 do begin

    if (t[k+1,j]>f) or (f>f)then break;

    f:=min(f,max(f,t[k+1,j]));

    end;

    end;

    ans:=f[m,n];

    total:=0;

    r:=n;

    x1:=0;

    for i:=n downto 1 do begin

    inc(total,s[i]);

    if total>ans then begin

    inc(x1);

    mm[x1,1]:=i+1;

    mm[x1,2]:=r;

    r:=i;

    total:=s[i];

    end;

    end;

    if total>=0 then begin

    inc(x1);

    mm[x1,1]:=1;

    mm[x1,2]:=r;

    end;

    for i:=x1 downto 1 do

    writeln(mm,' ',mm);

    end;

    begin

    init;

    main;

    end.

  • -1
    @ 2009-10-03 16:47:23

    就用o(n^3)动规

  • -1
    @ 2009-09-03 14:14:08

    那个“from飞过海”里的from拼错了。。。

    还有时限问题:我用的是O(N^3)的。可是:

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

    这。。。。???

  • -1
    @ 2009-08-27 17:32:28

    编译通过...

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

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

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

    ├ 测试数据 04:答案错误... ├ 标准行输出 28 29

     ├ 错误行输出 205 2....

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

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

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

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

    ├ 测试数据 09:答案错误... ├ 标准行输出 83 8...

     ├ 错误行输出 324 ....

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

    求助,有和我错的一样的吗?为什么?

  • -1
    @ 2009-08-27 16:46:10

    How to DP ????

  • -1
    @ 2009-08-27 16:09:35

    不工作的居然不要输出~

  • -1
    @ 2009-08-27 17:00:27

    4 6 9 输出长,数据是何种类型,我为什么错啊

  • -1
    @ 2009-08-27 14:55:04

    飞过海老兄,你心太狠,我交了六次,前五次 结果如下:

    编译通过... ├ 测试数据 01:答案错误...程序输出比正确答案长 ├ 测试数据 02:答案错误...程序输出比正确答案长 ├ 测试数据 03:答案错误...程序输出比正确答案长 ├ 测试数据 04:答案错误...程序输出比正确答案长 ├ 测试数据 05:答案错误...程序输出比正确答案长 ├ 测试数据 06:答案错误...程序输出比正确答案长 ├ 测试数据 07:答案错误...程序输出比正确答案长 ├ 测试数据 08:答案错误...程序输出比正确答案长 ├ 测试数据 09:答案错误...程序输出比正确答案长 ├ 测试数据 10:答案错误...程序输出比正确答案长 ------------------------- Unaccepted 有效得分:0 有效耗时:0ms 编译通过... ├ 测试数据 01:答案错误...程序输出比正确答案长 ├ 测试数据 02:答案错误...程序输出比正确答案长 ├ 测试数据 03:答案错误...程序输出比正确答案长 ├ 测试数据 04:答案错误...程序输出比正确答案长 ├ 测试数据 05:答案错误...程序输出比正确答案长 ├ 测试数据 06:答案错误...程序输出比正确答案长 ├ 测试数据 07:答案错误...程序输出比正确答案长 ├ 测试数据 08:答案错误...程序输出比正确答案长 ├ 测试数据 09:答案错误...程序输出比正确答案长 ├ 测试数据 10:答案错误...程序输出比正确答案长 ------------------------- Unaccepted 有效得分:0 有效耗时:0ms 编译通过... ├ 测试数据 01:答案错误...程序输出比正确答案长 ├ 测试数据 02:答案错误...程序输出比正确答案长 ├ 测试数据 03:答案错误...程序输出比正确答案长 ├ 测试数据 04:答案错误...程序输出比正确答案长 ├ 测试数据 05:答案错误...程序输出比正确答案长 ├ 测试数据 06:答案错误...程序输出比正确答案长 ├ 测试数据 07:答案错误...程序输出比正确答案长 ├ 测试数据 08:答案错误...程序输出比正确答案长 ├ 测试数据 09:答案错误...程序输出比正确答案长 ├ 测试数据 10:答案错误...程序输出比正确答案长 ------------------------- Unaccepted 有效得分:0 有效耗时:0ms 编译通过... ├ 测试数据 01:答案错误...程序输出比正确答案长 ├ 测试数据 02:答案错误...程序输出比正确答案长 ├ 测试数据 03:答案错误...程序输出比正确答案长 ├ 测试数据 04:答案错误...程序输出比正确答案长 ├ 测试数据 05:答案错误...程序输出比正确答案长 ├ 测试数据 06:答案错误...程序输出比正确答案长 ├ 测试数据 07:答案错误...程序输出比正确答案长 ├ 测试数据 08:答案错误...程序输出比正确答案长 ├ 测试数据 09:答案错误...程序输出比正确答案长 ├ 测试数据 10:答案错误...程序输出比正确答案长 ------------------------- Unaccepted 有效得分:0 有效耗时:0ms 编译通过... ├ 测试数据 01:答案错误...程序输出比正确答案长 ├ 测试数据 02:答案错误...程序输出比正确答案长 ├ 测试数据 03:答案错误...程序输出比正确答案长 ├ 测试数据 04:答案错误...程序输出比正确答案长 ├ 测试数据 05:答案错误...程序输出比正确答案长 ├ 测试数据 06:答案错误...程序输出比正确答案长 ├ 测试数据 07:答案错误...程序输出比正确答案长 ├ 测试数据 08:答案错误...程序输出比正确答案长 ├ 测试数据 09:答案错误...程序输出比正确答案长 ├ 测试数据 10:答案错误...程序输出比正确答案长 ------------------------- Unaccepted 有效得分:0 有效耗时:0ms

    第六次,我赌上人品,一个字不改,他他他他----竟然过了!!!!!!!!!!!!!! {虽然没有秒杀}

    varm,n,i,j,k,kk,l,x,y,z,o:longint;sum,f:array[-1..10000]of longint;p:array[-1..1200,-1..1200]of longint;function max(a,b:longint):longint;beginif a>b then max:=a else max:=b;end;function min(a,b:longint):longint;beginif a>b then min:=b else min:=a;;end;beginreadln(m,k);for i:=1 to m do beginread (z);sum[i]:=sum+z;if z>l thenl:=z;end;for i:=0 to m dofor j:=0 to m dop:=maxint;for i:=1 to k dofor j:=i to m-k+i dofor kk:=i-1 to j dop:=min(p,max(p,sum[j]-sum[kk-1]));i:=k;j:=m-1;o:=m;while j>0 dobeginwhile sum[o]-sum[j]

  • -1
    @ 2009-08-27 09:34:31

    二分答案=秒杀

  • -1
    @ 2009-08-27 08:13:41

    来自SPOJ.如果没看错的话。

  • -1
    @ 2009-08-27 01:39:46

    编译通过...

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

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

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

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

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

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

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

    ├ 测试数据 08:答案正确... 853ms

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

    ├ 测试数据 10:答案正确... 56ms

    O(N^3)的算法,不知道秒杀的大牛是用什么方法的?

    DP求出最短时间,然后贪心,不知道为什么用单纯的DP只有20分,可以是我写错了~

  • -2
    @ 2009-10-18 12:12:00

    编译通过...

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

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

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

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

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

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

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

    ├ 测试数据 08:答案正确... 4853ms

    ├ 测试数据 09:答案正确... 244ms

    ├ 测试数据 10:答案正确... 822ms

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

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

    ................

  • -2
    @ 2009-09-07 00:14:18

    明明就只是个动规...咋要搞的这么恼火......

    老师布置了一道一样的题,交老师那能ac的题,到这里只有20分.....

    我晕掉了,交了5次....

    另外,庆祝一下,AC第100道题虽然很艰难....

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

    编译通过...

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

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

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

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

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

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

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

    ├ 测试数据 08:答案正确... 572ms

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

    ├ 测试数据 10:答案正确... 41ms

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

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

  • -2
    @ 2009-09-05 18:07:46

    编译通过...

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

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

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

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

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

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

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

    ├ 测试数据 08:答案正确... 56ms

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

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

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

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

    SUNNY好慢啊

  • -2
    @ 2009-08-29 17:24:43

    什么破题,输出可以少于k行(前面的人不干事就不用输出)……

    二分答案+DP,还用了点单调性,复杂度O(31*m*k)……没秒掉……

信息

ID
1639
难度
7
分类
动态规划 点击显示
标签
(无)
递交数
1102
已通过
194
通过率
18%
被复制
1
上传者