题解

51 条题解

  • 3
    @ 2017-03-12 15:26:36
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #define rn 10000
    using namespace std;
    
    int n,m,f[rn+1];
    
    struct hw_1
    {
        int x,t;
    }a[rn+1];
    
    int main()
    {
        scanf("%d%d",&n,&m);
        int x=m;
        for (int i=1;i<=m;i++)
            scanf("%d%d",&a[i].x,&a[i].t);
        memset(f,0,sizeof(f));
        for (int i=n;i>=1;i--)
        {
            if (a[x].x!=i)
                f[i]=f[i+1]+1;
            else
                while (a[x].x==i)
                {
                    f[i]=max(f[i],f[a[x].t+i]);
                    x--;
                }
        }
        printf("%d\n",f[1]);
    }
    
  • 0
    @ 2020-08-28 15:12:55

    #include <bits/stdc++.h>
    using namespace std;
    int n,k;
    int f[99999];
    struct ha{
    int p;
    int t;
    }a[99999];
    int main(){
    cin>>n>>k;
    int x=k;
    for(int i=1; i<=k; i++){
    cin>>a[i].p>>a[i].t;
    }
    for(int i=n; i>=1; i--){
    if(a[x].p!=i){
    f[i]=f[i+1]+1;
    }
    else{
    while(a[x].p==i){
    f[i]=max(f[i],f[a[x].t+i]);
    x--;
    }
    }
    }
    cout<<f[1];
    return 0;
    }
    //不对的话寄刀片

  • 0
    @ 2020-05-15 22:01:04

    LIS入门

    #include<iostream>
    using namespace std;
    const int MAXN=10000+1;
    struct Node
    {
        int s;
        int e;
    };
    bool mymax(int a,int b)
    {
        if(a>b)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    int main()
    {
        int t,n;
        Node hw[MAXN];
        int dp[MAXN]={0};
        cin>>t>>n;
        for(int i=0;i<n;i++)
        {
            cin>>hw[i].s;
            cin>>hw[i].e;
        }
        for(int i=t;i>0;i--)
        {
            bool k=true;
            int max=0;
            for(int j=n-1;j>=0;j--)
            {
                if(hw[j].s==i)
                {
                    k=false;
                    if(dp[i+hw[j].e]>max)
                    {
                        max=dp[i+hw[j].e];
                    }
                }
            }
            if(!k)
            {
                dp[i]=max;
            }
            if(k)
            {
                dp[i]=dp[i+1]+1;
            }
        }
        cout<<dp[1]<<endl;
        return 0;
    }
    
    
    
  • 0
    @ 2018-08-08 11:43:50

    dp~~~水题
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n,k,p[11000],t[11000],f[11000];
    int main()
    {
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)
    {
    scanf("%d%d",&p[i],&t[i]);
    }
    memset(f,0,sizeof(f));
    for(int i=n;i>=1;i--)
    {
    if (p[k]!=i)
    f[i]=f[i+1]+1;
    else
    while (p[k]==i)
    {
    f[i]=max(f[i],f[t[k]+i]);
    k--;
    }
    }
    printf("%d\n",f[1]);
    return 0;
    }

  • 0
    @ 2016-11-10 19:02:32

    DP方程:
    f[i]=f[i+1]+1(p[j]<>i)
    f[i]=max(f[i],f[t[j]+i])(p[j]=i)
    ```pascal
    program pooroi;
    var n,k,i,j,r,x,y:longint;
    p,t,f:array[0..10000]of longint;

    function max(a,b:longint):longint;
    begin
    if a>b then exit(a) else exit(b);
    end;

    begin
    readln(n,k);
    for i:=1 to k do
    readln(p[i],t[i]);

    f[n+1]:=0;
    j:=k;

    for i:=n downto 1 do
    begin
    f[i]:=0;
    if p[j]<>i then f[i]:=f[i+1]+1
    else
    while p[j]=i do
    begin
    f[i]:=max(f[i],f[t[j]+i]);
    dec(j);
    end;
    end;

    writeln(f[1]);
    end.

  • 0
    @ 2014-08-16 00:29:17

    program p1577;
    var i,n,k,h:longint;
    a:array[0..10001,1..2] of longint;
    f:array[1..10001] of longint;
    //
    function max(a,b:longint):longint;
    begin
    if a>b then exit(a)
    else exit(b);
    end;
    //
    begin
    read(n,k);
    for i:=1 to k do read(a[i,1],a[i,2]);
    for i:=n downto 1 do
    begin
    h:=k;
    while (h>0) and (a[h,1]>i) do dec(h);
    if (h<=0) or (a[h,1]<>i) then f[i]:=f[i+1]+1
    else begin while (a[h,1]=i) and (h>0) do begin f[i]:=max(f[i+a[h,2]],f[i]);dec(h);end;end;
    end;
    write(f[1]);
    end.

  • 0
    @ 2009-11-19 19:46:36

    #include

    using namespace std;

    int dp[10001];

    int a[10001],c[10001],d[10001];

    int n,m;

    int main ()

    {

    int i,j;

    cin>>n>>m;

    for (i=1;i>a[i]>>c[i];

    d[a[i]]=1;

    }

    dp[n+1]=0;

    for (j=n;j>=1;j--)

    {

    if (d[j])

    {

    for(int l=1;l

  • 0
    @ 2009-11-04 16:45:58

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    O(2nlogm)的算法……秒杀!

  • 0
    @ 2009-11-03 19:41:40

    纯水题= =、

  • 0
    @ 2009-10-26 16:43:31

    var

    i,j,n,k:longint;

    s,t:array[1..9999]of longint;

    f:array[1..10000]of longint;

    begin

    readln(n,k);

    f[n+1]:=0;

    for i:=1 to k do read(s[i],t[i]);

    j:=k;

    for i:= n downto 1 do

    begin

    f[i]:=0;

    if s[j]i then f[i]:=f+1

    else

    while s[j]=i do

    begin

    if f[i+t[j]]>f[i] then f[i]:=f[i+t[j]];

    j:=j-1;

    end;

    end;

    writeln(f[1]);

    end.

  • 0
    @ 2009-10-26 12:28:55

    我先做的1634

    结果改了两个字交上去

    竟然AC了!

  • 0
    @ 2009-10-18 14:26:23

    无需排序!鉴定完毕。

  • 0
    @ 2009-10-11 22:49:24

    尼克的任务

  • 0
    @ 2009-09-25 11:10:38

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    var s,t,f:array[0..10000]of integer;

    n,k,j,i:longint;

    begin

    readln(n,k);

    for i:=1 to k do read(s[i],t[i]);

    fillchar(f,sizeof(f),0);j:=k;

    for i:=n downto 1 do

    begin

    if s[j]i then f[i]:=f+1

    else

    while s[j]=i do

    begin

    if f[i]

  • 0
    @ 2009-09-14 20:47:41

    异乎寻常的囧,,竟然交了三次。。。。。。。

  • 0
    @ 2009-09-14 18:13:00

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

    R1530292 Accepted 100 From linyinghao-

      P1577 FPC Vivid Puppy 2009-9-14 18:12:01

    From 1s

    可怜的Oliver 冰尘e溶化邀请赛 系列

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    program vijos1577;

    var k,i,j,n:integer;

    p,t,f:array[1..10000]of integer;

    q:array[1..10000]of boolean;

    begin

    read(n,k);

    for i:=1 to k do

    begin

    read(p[i],t[i]);

    q[p[i]]:=true;

    end;

    for i:=n downto 1 do

    if not(q[i]) then f[i]:=f+1

    else

    for j:=1 to k do

    if p[j]=i then

    if f[i]

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

    此题数据非常水,无须排序!!

    经鉴定,此题密度近似为1

  • 0
    @ 2009-09-06 11:20:36

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    var p,t,f:array[0..10003]of longint;

    i,n,k,x,j:longint;

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

    begin

    if x>y then max:=x else max:=y;

    end;

    begin

    readln(n,k);

    for i:=1 to k do readln(p[i],t[i]);

    for i:=n downto 1 do

    begin

    x:=0;

    for j:=1 to k do if p[j]=i then x:=1;

    if x=0 then f[i]:=f+1

    else for j:=1 to k do if p[j]=i then f[i]:=max(f[i],f[i+t[j]]);

    end;

    writeln(f[1]);

    end.

    Flag    Accepted

    题号   P1577

    类型(?)   动态规划

    通过   211人

    提交   345次

    通过率   61%

    难度   1

    为什么又一次AC啊....

  • 0
    @ 2009-08-28 10:13:14

    绝对是人品RP有问题,倒推却打成最少的时间=.=||

  • 0
    @ 2009-08-27 14:24:21

    囧...

    交了两遍,发现正推比较费劲

信息

ID
1577
难度
3
分类
动态规划 | 动态规划 | LIS 点击显示
标签
(无)
递交数
1414
已通过
740
通过率
52%
被复制
2
上传者