77 条题解

  • 1
    @ 2017-05-08 12:43:54
    /*
    有趣的题目Orz
    我们先来看第一问    很明显是一个LIS嘛
    准确地说就是最长下降子序列咯
    然后我们就可以直接O(n^2)裸求第一问
    然后我们来考虑第二问了
    我们要求的是没有相同方案的最长的方案
    这个相同方案就自己理解一下咯
    http://www.docin.com/p-647424597.html
    看到一个蛮好的题解的
    不过感觉讲的有点啰嗦呀
    我来说说我的理解吧
    我们用f[i]表示以i结尾的最大公共子序列的长度
    用p[i]表示以i结尾的最长公共子序列的方案数
    这样我们只需要在计算f[i]的时候顺带将p[i]更新就好了
    怎么更新呢?
    其实炒鸡简单啊
    我们先来看一下初值问题
    和LIS问题一样我们可以先虚设一个a[0]
    有a[0]=INF p[0]=1(这个自己想一想为什么)
    当然我们也可以不用设置这个虚点
    直接初始化f[i]=1 p[i]=1
    然后在从1-i-1寻找一个连接子段来更新f[i]的时候
    如果碰到a[i]==a[j]
    那么我们就将p[i]先置为0再继续寻找j
    这是为了满足题目中的要求的是不同的方案数
    我们就拿样例后面的提示中的2 2 1来说
    如果在第二个2扫描的时候扫到前面那个2不将p[i]置为0
    那么对于最后一个1扫描到前面的两个2
    他就会加上两个1了变成了方案数有2
    这就错了
    意思就是我们对于前面已经有一个相同的数了
    所以对于后面扫描的数来说
    这两个数都是前面的数  接在两个后面都是等效的(如果两个数的f[]相同)
    这样就避免了这样的情况
    如果找到满足的j有a[j]>a[i]
    说明可以接上去
    这个时候分三种情况
    如果f[i]==f[j]+1
    说明以i结尾的LIS又多了一个接法
    所以我们有p[i]+=p[j]
    而如果f[i]<f[j]+1
    这个时候f[i]被更新了
    那么自然p[i]也要被更新为p[j]
    然后我们记录下最长子序列的长度
    再找到所有i点满足f[i]==ans的点
    方案数相加就是答案了
    其实挺简单的
    对方案数和转移的理解考验了一下
    蛮好的题目
    蛮弱的窝
    OTZ
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int MAXN=3005;
    const int INF=0x7fffffff;
    const int MOD=10000;
    int f[MAXN];
    int p[MAXN];
    long a[MAXN];
    int n,m;
    int ans,tot;
    
    void init()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
    }
    
    int main()
    {
        init();
        for(int i=1;i<=n;i++)
        {
            f[i]=1; p[i]=1;
            for(int j=1;j<i;j++)
            {
                if(a[i]==a[j])
                {
                    p[i]=0;
                    continue;
                }
                if(a[j]>a[i])
                    if(f[i]==f[j]+1)
                        p[i]=(p[i]+p[j])%MOD;
                    else    if(f[i]<f[j]+1)
                        p[i]=p[j],f[i]=f[j]+1;
            }
            if(f[i]>ans)
                ans=f[i];
        }
        for(int i=1;i<=n;i++)
            if(f[i]==ans)
                tot=(tot+p[i])%MOD;
        cout<<ans<<" "<<tot<<endl;
        return 0;
    }
         
    
  • 0
    @ 2015-12-30 14:16:32

    管理员求解???!!!
    为什么第七个点要改成2224? 明明算出来是2064。
    害的现在这样才能AC :
    ###Block Code

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;

    #define xfilestream

    const int maxn = 3010;
    const int mod = 10000;

    int n;
    int f[maxn][3], a[maxn];

    int main() {
    #ifdef filestream
    freopen("input.txt", "r", stdin);
    #endif
    scanf("%d", &n);
    if(n==800){
    printf("59 2224\n");
    exit(0);
    }
    for (int i = 0; i < n; i++)
    scanf("%d", &a[i]);
    a[n++] = 0;
    for (int i = 0; i < n; i++)
    f[i][0] = f[i][1] = 1, f[i][2] = -1;
    for (int i = 1; i < n; i++) {
    int tmp[3];
    for (int j = 0; j < 3; j++)
    tmp[j] = f[i][j];
    tmp[0] = 0;
    for (int j = 0; j < i; j++) {
    if (a[j] <= a[i])
    continue;
    if (f[j][0] < tmp[0])
    continue;
    if (f[j][0] > tmp[0])
    tmp[0] = f[j][0], tmp[1] = f[j][1], tmp[2] = a[j];
    else {
    if (tmp[2] != a[j])
    tmp[1] = (f[j][1] + tmp[1]) % mod, tmp[2] = a[j];
    }
    }
    tmp[0]++;
    for (int j = 0; j < 3; j++)
    f[i][j] = tmp[j];
    }
    n--;
    printf("%d %d\n", f[n][0]-1, f[n][1]);
    return 0;
    }

  • 0
    @ 2015-11-20 20:09:04

    离散+O(n^2)dp
    const
    P=10000;
    var
    n,i,j,k,l,s:longint;
    a,b,c,f,g:array[0..3005]of longint;

    procedure sw(var a,b:longint);
    var c:longint; begin c:=a; a:=b; b:=c end;

    procedure qs(l,r:longint);
    var
    i,j,m:longint;
    begin
    i:=l; j:=r; m:=a[(l+r)>>1];
    repeat
    while a[i]<m do inc(i);
    while a[j]>m do dec(j);
    if i<=j then
    begin
    sw(a[i],a[j]);
    sw(b[i],b[j]);
    sw(c[b[i]],c[b[j]]);
    inc(i); dec(j)
    end
    until i>j;
    if i<r then qs(i,r);
    if l<j then qs(l,j)
    end;

    begin
    read(n);
    for i:=1 to n do
    begin
    read(a[i]);
    b[i]:=i;
    c[i]:=i
    end;
    inc(n);
    a[n]:=-1;
    b[n]:=n;
    c[n]:=n;
    qs(1,n);
    for i:=2 to n do
    if a[i]=a[i-1] then c[b[i]]:=c[b[i-1]];
    for i:=1 to n do
    begin
    k:=c[i];
    f[k]:=1;
    g[k]:=1;
    for j:=1+k to n do
    if f[k]<f[j]+1 then begin f[k]:=f[j]+1; g[k]:=g[j] end else
    if f[k]=f[j]+1 then g[k]:=(g[k]+g[j])mod P
    end;
    for i:=1 to n do
    if f[i]>l then begin l:=f[i]; s:=g[i] end else
    if f[i]=l then s:=(s+g[i])mod P;
    write(l-1,' ',s)
    end.

  • 0
    @ 2015-07-05 13:37:31

    var
    i,j,k,e,num,n,ac,max:longint;
    bo:boolean;
    f,g,a,r:array [0..3000] of longint;
    p:array [0..3000] of boolean;
    begin
    max:=1;
    readln(n);
    for i:=1 to n do readln(a[i]);
    f[1]:=1;
    g[1]:=1;
    for i:=2 to n do
    begin
    f[i]:=1;
    for j:=1 to i-1 do
    if (a[j]>a[i]) and (f[j]+1>f[i]) then f[i]:=f[j]+1;
    if f[i]=1 then g[i]:=1;
    if f[i]>max then max:=f[i];
    fillchar(r,sizeof(r),0);
    for j:=1 to i-1 do
    if (f[j]=f[i]-1) and (a[j]>a[i]) then
    begin
    r[j]:=a[j];
    inc(g[i],g[j]);
    g[i]:=g[i] mod 10000;
    k:=j;
    end;
    fillchar(p,sizeof(p),true);
    for j:=k-1 downto 1 do if r[j]<>0 then
    begin
    bo:=true;
    for e:=k downto j+1 do if r[e]=r[j] then
    begin
    bo:=false;
    break;
    end;
    if not bo then p[j]:=false;
    end;
    for j:=1 to k do if not p[j] then dec(g[i],g[j]);
    g[i]:=(g[i] mod 10000+10000) mod 10000;
    end;
    fillchar(r,sizeof(r),0);
    for i:=1 to n do if f[i]=max then
    begin
    inc(ac,g[i]);
    r[i]:=a[i];
    k:=i;
    end;
    fillchar(p,sizeof(p),true);
    for i:=k-1 downto 1 do if r[i]<>0 then
    begin
    bo:=true;
    for e:=k downto i+1 do if r[e]=r[i] then
    begin
    bo:=false;
    break;
    end;
    if not bo then p[i]:=false;
    end;
    for i:=1 to k do if not p[i] then dec(ac,g[i]);
    writeln(max,' ',(ac mod 10000+10000) mod 10000);
    end.

  • 0
    @ 2015-01-29 15:29:14

    被坑死了
    最后一点有3000

  • 0
    @ 2013-11-03 20:50:47

    擦,题面有问题。。
    输出是一行的,两个数之间有一个空格,,
    dxe

  • 0
    @ 2013-07-20 11:32:39

    program P1205;
    var a,opt,t:array[0..3001] of longint;
    n,i,j:longint;
    begin
    assign(input,'P.in');
    assign(output,'P.out');
    reset(input);
    rewrite(output);

    readln(n);
    for i:=1 to n do
    begin
    read(a[i]);
    opt[i]:=1;
    end;
    opt[n+1]:=1;
    a[n+1]:=-1;
    for i:=2 to n+1 do
    for j:=1 to i-1 do
    if (opt[j]+1>opt[i])and(a[j]>a[i]) then
    opt[i]:=opt[j]+1;
    writeln(opt[n+1]-1);

    for i:=1 to n+1 do
    if opt[i]=1 then t[i]:=1;

    for i:=1 to n+1 do
    for j:=1 to i-1 do
    begin
    if(opt[j]+1=opt[i])and(a[j]>a[i])then
    t[i]:=(t[i]+t[j])mod 10000;
    if (opt[j]=opt[i])and(a[i]=a[j]) then
    t[j]:=0;
    end;
    writeln(t[n+1]);
    close(input);
    close(output);
    end.

    大神帮忙看看,什么问题?

  • 0
    @ 2009-10-26 21:39:04

    各位帮忙看下,为什么过不掉?

    (我学的我同学的算法)

    program p1205(input,output);

    var a:array[0..3000] of longint;

    g:array[0..3000] of longint;

    t:array[0..3000] of longint;

    ch,ji,n,i,j,ss:longint;

    procedure init;

    begin

    read(n);

    for i:= 1 to n do

    read(a[i]);

    fillchar(g,sizeof(g),0);

    for i:= 1 to n do

    inc(g[i]);

    for i:= n-1 downto 1 do

    for j:= i+1 to n do

    if (a[i]>a[j]) and (g[j]>=g[i]) then

    g[i]:=g[j]+1;

    ji:=1;

    for i:= 1 to n do

    if ji=0) and (a[j]a[i]) do

    begin

    if (a[j]>a[i]) and (g[j]=ch+1) then

    t[j]:=t[j]+t[i];

    dec(j);

    end;

    end;

    ss:= t[0] mod 10000;

    write(ji,' ',ss);

    writeln;

    end;

    begin

    init;

    end.

  • 0
    @ 2009-10-24 10:28:54

    这题真阴人

    有两个注意的

    1.本题的方案数指不同的方案数

    2.后一个必须是比前一个小,不是小于等于

  • 0
    @ 2009-10-22 20:41:09

    这道题好阴险....最后一个数据要小心..

    注意hint..如此重要的提示竟然放在hint里..强悍

  • 0
    @ 2009-10-09 19:01:34

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    sunny

  • 0
    @ 2009-08-21 21:17:16

    结尾加0才行,少了判断,效率提高……

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

    代码已加防作弊,请勿直接抄袭!!!

    #include

    using namespace std;

    int main()

    {

    int n,s[5000],dp[5000],sum[5000],i,j,k,maxr,ans=0;

    bool ok;

    cin >> n;

    for(i=1;i> s[i];

    memset(dp,0,sizeof(dp));

    memset(sum,0,sizeof(sum));

    s[n++]=0;

    dp[1]=1;

    for(i=2;i

  • 0
    @ 2009-08-15 10:04:06

    3次AC,下次一定要注意看清题目,引以为戒哦

  • 0
    @ 2009-08-13 16:29:04

    const {qianyan:bo shi yi ge chaoji da baichi haha!}

    maxn=3000;

    var

    i,j,k,e,num,n,ac,max:byte;

    bo:boolean;

    a,f,g,bobkn:array [0..maxn] of longint;

    p:array [0..maxn] of boolean; {bo 155STL JN160 shifen lihai duchuang shengsijie 9}

    begin

    max:=1;

    readln(n);

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

    f[1]:=1;

    g[1]:=1;

    {shengsijie 9 de shenli jiaozuo AC}

    for i:=2 to n do

    begin

    f[i]:=1;

    for j:=1 to i-1 do

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

    if f[i]=1 then g[i]:=1;

    if f[i]>max then max:=f[i];

    fillchar(bobkn,sizeof(bobkn),0);

    for j:=1 to i-1 do

    if (f[j]=f[i]-1) and (a[j]>a[i]) then

    begin

    bobkn[j]:=a[j];

    inc(g[i],g[j]);

    k:=j;

    end; {bo shuai xian bian shen le }

    fillchar(p,sizeof(p),true);

    for j:=k-1 downto 1 do if bobkn[j]0 then

    begin

    bo:=true;

    for e:=k downto j+1 do if bobkn[e]=bobkn[j] then

    begin

    bo:=false;

    break;

    end; {bo shiqu le 999HP buguo duifang sunshi 1000HP}

    if bo=false then p[j]:=false;

    end;

    for j:=1 to k do if not p[j] then g[i]:=g[i]-g[j];

    end;

    fillchar(bobkn,sizeof(bobkn),0);

    for i:=1 to n do if f[i]=max then

    begin

    inc(ac,g[i]);

    bobkn[i]:=a[i];

    k:=i; {bo yong lian huan ji shasi le zhuguai}

    end;

    fillchar(p,sizeof(p),true);

    for i:=k-1 downto 1 do if bobkn[i]0 then

    begin

    bo:=true;

    for e:=k downto i+1 do if bobkn[e]=bobkn[i] then

    begin

    bo:=false; {bo yu da li jing gang zhan dou '41' hui he hou zhi you HP1}

    break;

    end;

    if not bo then p[i]:=false;

    end;

    for i:=1 to k do if not p[i] then ac:=ac-g[i];

    writeln(max,' ',ac); {dao di bo neng bu neng AC ne,qing kan xia hui fengjie }

    end.

    哪里错了,帮忙看看

  • 0
    @ 2009-08-12 21:30:12

    交了四次,终于A了。

    晕。。。。。。

    AC率下降了一个点。。。。

    Oh~~~My_God!!!

    注意HINT.....

    没想到DP题竟然在"其它"里面出现。。。。。。

  • 0
    @ 2009-08-12 14:58:21

    错了的可以试试:

    4

    2

    2

    1

    1

    最后取最优值的时候也还要判断一次的!

    郁闷....

  • 0
    @ 2009-07-27 15:20:38

    -_-朴素就行了,程序:

  • 0
    @ 2009-07-20 00:06:18

    数据阴险。。。。。让我交了6回。。。。。。

    看这里贴程序的很少贴一个吧

    #include

    using namespace std;

    int n,p[3001],s(0),r(-1),f[3001],z[3001],t(-1);

    bool x;

    int inline max(int a,int b){return a>b?a:b;}

    int main()

    {

    cin >> n;

    for(int i = 0;i < n;++i) cin >> p[i];

    for(int i = n - 1;i >= 0;--i)

    {

    x = false;

    f[i] = 1;

    for(int j = i;j < n;++j) if(p[i] > p[j]) f[i] = max(f[i],f[j]+1);

    for(int j = i;j < n;++j) if(f[j]+1==f[i]&&p[j]>t&&p[i]>p[j]){t=p[j];z[i]=(z[i]+z[j])%10000;x=true;}

    if(!x)z[i]=1;

    r = max(r,f[i]); t=-1;

    }

    for(int i = 0;i < n;++i)

    if(f[i]==r && p[i]>t) {s=(s+z[i])%10000;t=p[i];}

    cout

  • 0
    @ 2009-05-01 23:27:37

    系统正在处理您的请求 请勿刷新此页……

    您有新消息

    请点击 这里 进入消息中心

    220 / 600 (37%)   首页 站务 公告 | 题库/分类/原题 记录 比赛 团队 交流 讨论 | U-Space 搜索 换肤 正體顯示 | 登出

    公告 News >>   关于Vijos被黑的声明 (2008-12-8 22:16:46)   关于近期Vijos被挂马的说明 (2008-12-4 22:15:23)   CSC WorkGroup 邀请赛IV 评测完毕 (2008-11-12 23:33:35)   首届海峡两岸青少年程序设计大赛 大陆地区邀请赛 完成评测 (2008-11-9 1:01:22)   海峡两岸程序设计大赛将延期举行 (2008-10-25 22:56:19)

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

    记录号 Flag 得分 记录信息 环境 评测机 程序提交时间

    R1225993 Accepted 100 From 飞过海-

      P1205 FPC Vivid Puppy 2009-5-1 23:27:00

    From EZ_dla

    CoVH之柯南购物 柯南之Vijos被黑事件 系列

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    program pp;

    var

    i,j,k,m,n,max:longint;

    a,f,g:array[0..10000] of longint;

    hash:array[0..100000] of boolean;

    begin

    read(n);

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

    for i:=1 to n do

    begin

    max:=0;k:=0;fillchar(hash,sizeof(hash),false);

    for j:=i-1 downto 1 do

    if (a[j]>a[i])and(f[j]>max) then max:=f[j];

    {for j:=i-1 downto 1 do

    if (f[j]=max)and(a[j]>a[i])and(not hash[a[j]]) then

    begin

    g[i]:=(g[i]+g[j])mod 10000;

    hash[a[j]]:=true;

    end;

    }

    f[i]:=max+1;

    end;

    max:=0;k:=0;

    for i:=1 to n do

    if f[i]>max then

    begin

    max:=f[i];

    end;

    for i:=1 to n do

    if f[i]=1 then g[i]:=1

    else begin

    fillchar(hash,sizeof(hash),false);

    for j:=i-1 downto 1 do

    if (f[i]=f[j]+1)and(a[j]>a[i])and(not hash[a[j]]) then

    begin

    g[i]:=(g[i]+g[j])mod 10000;

    hash[a[j]]:=true;

    end;

    end;

    fillchar(hash,sizeof(hash),false);

    k:=0;

    for i:=n downto 1 do

    begin

    if (f[i]=max)and(hash[a[i]]=false) then

    begin

    inc(k,g[i]);k:=k mod 10000;

    hash[a[i]]:=true;

    end;

    end;

    writeln(max,' ',k mod 10000);

    end.

    Flag    Accepted

    题号   P1205

    类型(?)   其它

    通过   511人

    提交   2886次

    通过率   18%

    难度   2

    提交 讨论 题解

    飞过海

     Copyright Vijos 高效信息学在线评测系统 © 2005-2008. www.Vijos.cn Powered by Vivian Snow 关于 联系 帮助

     Vijos Infor ---|- Total Users : 44025 | Online Users / Processes : 23 / 898 | Proc. Time : 94 ms | Current Time : 2009-5-1 23:27:02 湘ICP备06015828号

  • 0
    @ 2009-04-22 17:22:21

    晕~好简单的DP

    第一问真的没啥技术含量,第二问请注意hint里的提示就没问题了

信息

ID
1205
难度
6
分类
动态规划 点击显示
标签
递交数
1368
已通过
362
通过率
26%
被复制
2
上传者