题解 - Vijos

1

caesar_199 LV 9 @ 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

有向无环图 LV 8 @ 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

有向无环图 LV 8 @ 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

FenXy LV 10 @ 2009-11-08 19:31:05

Flag 　　 Accepted

题号　　P1283

类型(?) 　　动态规划

通过　　500人

提交　　1442次

通过率　　35%

难度　　2

0

展翅雛龍 LV 10 @ 2009-11-03 21:20:01

值得一做。

0

xuketian LV 9 @ 2009-11-03 21:06:27

好题啊...

0

超子 LV 9 @ 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

zhh1993 LV 10 @ 2009-10-24 10:57:18

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

0

honghaijie LV 9 @ 2009-10-12 17:27:12

好题啊

一开始准备枚举长度

原来一个f就解决了

哈哈

0

Jungle LV 10 @ 2009-10-11 15:47:08

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

要详细要详细

0

chengrui LV 10 @ 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

474182029 LV 8 @ 2009-09-15 18:20:04

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

0

prince_hao LV 10 @ 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

hxlong LV 10 @ 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

陈亮宇 LV 10 @ 2009-08-11 14:43:10

int64!

0

怪盗~基德 LV 10 @ 2009-08-01 20:50:52

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

0

w122185976 LV 10 @ 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

stevenjiang LV 8 @ 2009-07-10 08:47:07

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

0

notblack LV 10 @ 2009-07-02 21:36:58

满足长度要求用

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

不满足用

f=max{f,f,0}

貌似要开INT64。

0

enwei LV 8 @ 2009-06-10 17:40:43

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

题解

56 条题解

佳佳的魔杖

信息

状态

开发

支持

题解

56 条题解

佳佳的魔杖

信息

状态

开发

支持

还没有账户？

登录