题解

56 条题解

  • 1
    @ 2016-05-31 16:34:42
    #include<iostream>
    #include<fstream>
    #include<algorithm>
    using namespace std;
    
    const int maxn = 1100;
    typedef long long ll;
    int n;
    int hi, lo;
    int l[maxn];
    int m[maxn];
    ll f[maxn][maxn];
    ll suml[maxn];
    ll summ[maxn];
    
    int main ()
    {
        //ifstream cin ("in.txt");
        cin >> n >> lo >> hi;
        for (int i = 1; i <= n; i++) {
            cin >> l[i];
            suml[i] = suml[i - 1] + l[i];
        }
        for (int i = 1; i <= n; i++) {
            cin >> m[i];
            summ[i] = summ[i - 1] + m[i];
        }
        for (int i = 1; i <=n; i++) {
            for (int j = 1; j <= i; j++) {
                if (suml[i] - suml[j - 1] >= lo && suml[i] - suml[j - 1] <= hi) {
                    f[i][j] = max (f[i - 1][j], max (f[i][j - 1], f[i - 1][j - 1] + summ[i] - summ[j - 1]));
                }
                else f[i][j] = max (f[i - 1][j], f[i][j - 1]);
            }
        }
        cout << f[n][n];
        return 0;
    }
    
  • 0
    @ 2015-09-27 10:09:18

    program P1283;
    var
    L,M:array[1..1000] of int64;
    Lsum,Msum:array[0..1000] of int64;
    Ans:array[1..1001,1..1001] of int64;
    n,Lo,Hi:longint;
    function max(a,b:int64):int64;
    begin
    if a>b then
    begin
    exit(a);
    end
    else
    begin
    exit(b);
    end;
    end;

    procedure init;
    var
    i:longint;
    begin
    readln(n,Lo,Hi);
    for i:=1 to n do
    begin
    read(L[i]);
    end;
    readln;
    for i:=1 to n do
    begin
    read(M[i]);
    end;
    readln;
    Lsum[0]:=0;
    Msum[0]:=0;
    for i:=1 to n do
    begin
    Lsum[i]:=Lsum[i-1]+L[i];
    Msum[i]:=Msum[i-1]+M[i];
    end;
    for i:=1 to n do
    begin
    Ans[n+1,i]:=0;
    end;
    end;
    procedure solve;
    var
    i,j:longint;
    begin
    for i:=n downto 1 do
    begin
    Ans[i,n+1]:=0;
    for j:=n downto i do
    begin
    if (Lsum[j]-Lsum[i-1]>hi) or (Lsum[j]-Lsum[i-1]<lo) then
    begin
    Ans[i,j]:=Ans[i,j+1];
    end
    else
    begin
    Ans[i,j]:=max(Ans[i,j+1],Ans[i+1,j+1]+Msum[j]-Msum[i-1]);
    end;
    Ans[i,j]:=max(Ans[i,j],Ans[i+1,max(j,i+1)]);
    end;
    end;
    end;
    procedure print;
    begin
    writeln(Ans[1,1]);
    end;
    begin
    init;
    solve;
    print;
    end.

  • 0
    @ 2015-09-27 10:09:01

    赶脚现在Vijos的计时越来越精确了……似乎没法秒杀……
    program P1283;
    var
    L,M:array[1..1000] of int64;
    Lsum,Msum:array[0..1000] of int64;
    Ans:array[1..1001,1..1001] of int64;
    n,Lo,Hi:longint;
    function max(a,b:int64):int64;
    begin
    if a>b then
    begin
    exit(a);
    end
    else
    begin
    exit(b);
    end;
    end;

    procedure init;
    var
    i:longint;
    begin
    readln(n,Lo,Hi);
    for i:=1 to n do
    begin
    read(L[i]);
    end;
    readln;
    for i:=1 to n do
    begin
    read(M[i]);
    end;
    readln;
    Lsum[0]:=0;
    Msum[0]:=0;
    for i:=1 to n do
    begin
    Lsum[i]:=Lsum[i-1]+L[i];
    Msum[i]:=Msum[i-1]+M[i];
    end;
    for i:=1 to n do
    begin
    Ans[n+1,i]:=0;
    end;
    end;
    procedure solve;
    var
    i,j:longint;
    begin
    for i:=n downto 1 do
    begin
    Ans[i,n+1]:=0;
    for j:=n downto i do
    begin
    if (Lsum[j]-Lsum[i-1]>hi) or (Lsum[j]-Lsum[i-1]<lo) then
    begin
    Ans[i,j]:=Ans[i,j+1];
    end
    else
    begin
    Ans[i,j]:=max(Ans[i,j+1],Ans[i+1,j+1]+Msum[j]-Msum[i-1]);
    end;
    Ans[i,j]:=max(Ans[i,j],Ans[i+1,max(j,i+1)]);
    end;
    end;
    end;
    procedure print;
    begin
    writeln(Ans[1,1]);
    end;
    begin
    init;
    solve;
    print;
    end.

  • 0
    @ 2009-11-08 19:31:05

    Flag    Accepted

    题号   P1283

    类型(?)   动态规划

    通过   500人

    提交   1442次

    通过率   35%

    难度   2

  • 0
    @ 2009-11-03 21:20:01

    值得一做。

  • 0
    @ 2009-11-03 21:06:27

    好题啊...

  • 0
    @ 2009-11-04 17:37:31

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    =======================糊涂的分割线=====================

    program v1283;

    var f:array[0..1001,0..1001] of int64;

    w,l:array[0..1001] of int64;

    i,j:longint;

    n,s,e,m,x:int64;

    function max(a,b,c:int64):int64;

    begin

    max:=a;

    if b>max then max:=b;

    if c>max then max:=c;

    end;

    function can(a,b:int64):boolean;

    begin

    can:=false;

    if (l-l[a-1]>=s)and(l-l[a-1]

  • 0
    @ 2009-10-24 10:57:18

    令人诧异的方程and令人纠结的int64....

  • 0
    @ 2009-10-12 17:27:12

    好题啊

    一开始准备枚举长度

    原来一个f就解决了

    哈哈

  • 0
    @ 2009-10-11 15:47:08

    求一个完整点的题解= =。

    要详细要详细

  • 0
    @ 2009-10-09 19:11:52

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    int64!!!!!!!2次AC!!!

    虽然我很猥琐的看oimaster大牛的题解.......ORZ

    好题!

  • 0
    @ 2009-09-15 18:20:04

    不懂这状态转移方程。。。。

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

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    f表示最后一根魔杖右边界为i左边界为j的方法的最大值

    另用ans数组记录最佳值 可以把复杂度降为n^2

    ans[i]表示最后一根魔杖左边界小于等于i的方法的最大值

    f=ans[j-1]+summ[j,i] (此长度可取)

    绝对精辟~

  • 0
    @ 2009-08-21 22:34:22

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    DP=AC

  • 0
    @ 2009-08-11 14:43:10

    int64!

  • 0
    @ 2009-08-01 20:50:52

    对这题的精妙彻底臣服,彻底无语,五体膜拜唐老鸭超级大神牛。

  • 0
    @ 2009-07-25 09:24:55

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    搞了N久,只因为没把mm和ll算进去!555~~~~~~~~

  • 0
    @ 2009-07-10 08:47:07

    边界条件是什么..输出一片0....

  • 0
    @ 2009-07-02 21:36:58

    满足长度要求用

    f=max{f,f,f+sum}

    不满足用

    f=max{f,f,0}

    貌似要开INT64。

  • 0
    @ 2009-06-10 17:40:43

    为什么用f=max{f,f,f+sum}不 过 呀 !!!

信息

ID
1283
难度
5
分类
动态规划 点击显示
标签
递交数
727
已通过
267
通过率
37%
被复制
1
上传者