题解

303 条题解

  • 0
    @ 2012-08-01 14:39:17

    #include

    using namespace std;

    int main()

    {

    int n,i,j,max,kk;

    int a[100],h[100],f[100];

    cin>>n;

    for(i=0;i>a[i];

    f[i]=1;

    h[i]=1;

    }

    for(i=1;i

  • 0
    @ 2012-08-02 14:43:00

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    点击查看代码

    动态规划——最长上升子序列和最长下降子序列

  • 0
    @ 2012-07-23 18:43:54

    很明显的LIS+LDS。。只需要注意最后在枚举中间人的时候要-1。。

  • 0
    @ 2010-07-27 13:00:25

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    程序代码:

    program p1098;

    var

    a,b,c:array[1..100] of integer;

    i,j,n,ans:integer;

    begin

    readln(n);

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

    fillchar(b,sizeof(b),0);

    fillchar(c,sizeof(c),0);

    for i:=1 to n do

    begin

    b[i]:=1;

    for j:=1 to i-1 do

    if (a[i]>a[j]) and (b[j]+1>b[i]) then b[i]:=b[j]+1;

    end;

    for i:=n downto 1 do

    begin

    c[i]:=1;

    for j:=i+1 to n do

    if (a[i]>a[j]) and (c[j]+1>c[i]) then c[i]:=c[j]+1;

    end;

    ans:=0;

    for i:=1 to n do

    if (b[i]+c[i]>ans) then ans:=b[i]+c[i];

    ans:=n-ans+1;

    write(ans);

    end.

  • 0
    @ 2010-07-16 18:14:00

    忐忑的交上去竟然一次AC了。

    枚举那位最高点同学,左边最长上升子序列(从左向右dp),右边对称(从右向左dp)。注意那位最高点同学不要算2次。

    #include "stdio.h"

    int N,T[101];

    int up(int k)

    {

    int i,j,F[101];

    for(i=0;i

  • 0
    @ 2010-07-15 21:38:47

    program chorus;

    var

    a:array[0..100]of integer;

    n,i,j,k:integer;

    l,r:array[0..100]of integer;

    begin

    assign(input,'chorus.in');

    assign(output,'chorus.out');

    reset(input);

    rewrite(output);

    readln(n);

    l[1]:=1;

    r[n]:=1;

    for i:=1 to n do

    read(a[i]);

    for i:=2 to n do

    for j:=n-1 downto 0 do

    begin

    if (a[j]l[i])

    then l[i]:=l[j]+1;

    end;

    for i:=n downto 1 do

    for j:=i+1 to n+1 do

    begin

    if (a[j]r[i])

    then r[i]:=r[j]+1;

    end;

    for i:=1 to n do

    begin

    k:=l[i]+r[i];

    if l[i]+r[i]>k

    then k:=l[i]+r[i];

    end;

    writeln(n-k+1);

    close(input);

    close(output);

    end.

  • 0
    @ 2010-07-08 10:00:25

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    program p1098;{hechangdui}

    var n:2..100;i,j:1..100;c:array[1..100,1..3] of 0..230;

    begin

    readln(n);

    for i:=1 to n do begin read(c);c:=0;c:=0 end;

    for i:=2 to n do

    for j:=1 to i-1 do

    if (c[j,1]=c) then c:=c[j,2]+1;

    for i:=n-1 downto 1 do

    for j:=n downto i+1 do

    if (c[j,1]=c) then c:=c[j,3]+1;

    j:=c[1,2]+c[1,3];

    for i:=2 to n do

    if j

  • 0
    @ 2009-11-19 22:11:13

    不过是最长递升和递降子序列啊

  • 0
    @ 2009-11-10 10:31:47

    #include

    int main()

    {

    int n,i,j,a[110],f[110]={0},g[110]={0},max;

    scanf("%d",&n);

    for(i=1;i

  • 0
    @ 2009-11-09 21:09:10

    AC的第一道DP题

    program P1098;

    var a,t,b:array[0..100] of integer;

    i,j,n,total:integer;

    begin

    readln(n);

    for i:=1 to n do

    read(t[i]);

    for i:=1 to n do begin

    a[i]:=1;

    for j:=0 to i-1 do

    if (t[i]>t[j])and(a[i]t[j])and(b[i]total then total:=a[i]+b[i];

    writeln(n-total+1);

    end.

  • 0
    @ 2009-11-09 21:08:50

    f[1]:=1; g[n]:=1;{初值}

    2 to n

    1 to i-1

    if a[i]>a[j] then

    begin

    if f[j]+1>f[i] then

    f[i]:=f[j]+1

    else if f[i]=0 then f[i]:=1;

    end

    else if f[i]=0 then f[i]:=1;

    n-1 downto 1

    n downto i+1

  • 0
    @ 2009-11-09 20:12:15

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    怎么全是pascal?,来个c的吧!

    int n,t[101]={0},min[101],max[101];

    void Init()

    {

    int i;

    scanf("%d",&n);

    for(i=1;ik)

    k=max[j];

    max[i]+=k;

    }

    }

    int DP_min()

    {

    int i,j,k;

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

    {

    k=0;

    for(j=i+1;jt[j]&&min[j]>k)

    k=min[j];

    min[i]+=k;

    }

    }

    void process()

    {

    int m=0,i;

    for(i=1;im)

    m=min[i]+max[i];

    printf("%d",n-m+1);

    }

    int main()

    {

    Init();

    DP_max();

    DP_min();

    process();

    return 0;

    }

  • 0
    @ 2009-11-07 22:58:35

    复习lis 发现忘得差不多了

  • 0
    @ 2009-11-07 17:36:40

    编译通过...

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-11-06 21:10:23

    同样的方法,都是正向反向各求一次最长不降序列,但求法略有不同

    因为粗心“n-i+1”写成了“i-n+1”

    悲剧~~~

    program p1098;

    var n,i,j,x:integer;

    t,h,a,b:array[1..100] of integer;

    f1,f2:text;

    begin

    assign(f1,'in.txt');

    assign(f2,'out.txt');

    reset(f1);

    rewrite(F2);

    readln(f1,n);

    for i:=1 to n do begin read(f1,t[i]); a[i]:=1; b[i]:=1; end;

    for i:=n downto 1 do h[n-i+1]:=t[i];

    for i:=2 to n do

    for j:=1 to i-1 do

    if (t[i]>t[j]) and (a[j]+1>a[i]) then a[i]:=a[j]+1;

    for i:=2 to n do

    for j:=1 to i-1 do

    if (h[i]>h[j]) and (b[j]+1>b[i]) then b[i]:=b[j]+1;

    x:=n-b[n];

    for i:=2 to n do

    if (n-a[i]-b[n-i+1]+1)

  • 0
    @ 2009-11-06 20:58:44

    编译通过...

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

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

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

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

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

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

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

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

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

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

    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++

    TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++

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

    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++

    TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++

    program ex;

    var n,i,j,max:longint;

    a,b,c:array[1..100] of longint;

    begin

    readln(n);

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

    for i:=1 to n do

    begin

    b[i]:=1;

    for j:=1 to i-1 do

    if (a[i]>a[j])and(b[j]+1>b[i]) then b[i]:=b[j]+1;

    end;

    for i:=n downto 1 do

    begin

    c[i]:=1;

    for j:=n downto i+1 do

    if (a[i]>a[j])and(c[j]+1>c[i]) then c[i]:=c[j]+1;

    end;

    for i:=1 to n do

    if b[i]+c[i]>max then max:=b[i]+c[i];

    writeln(n-max+1);

    end.

  • 0
    @ 2009-11-06 09:58:09

    纪念我的第38次AC好郁闷的数字...

    不加优化的lis就可以过了...

  • 0
    @ 2009-11-03 15:56:21

    AAAAA!=C water

  • 0
    @ 2009-11-03 13:24:56

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

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

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

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

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

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

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

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

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

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

    AC

信息

ID
1098
难度
5
分类
动态规划 | LIS 点击显示
标签
递交数
12818
已通过
4881
通过率
38%
被复制
19
上传者