#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]);
}

#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;
}
//不对的话寄刀片

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;
}

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;
}

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.

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.

#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

编译通过...

├ 测试数据 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)的算法……秒杀！

纯水题= =、

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.

我先做的1634

结果改了两个字交上去

竟然AC了！

无需排序！鉴定完毕。

尼克的任务

编译通过...

├ 测试数据 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]

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

记录号 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]

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

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

编译通过...

├ 测试数据 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啊....

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

囧...

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