# 51 条题解

• @ 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]);
}
``````
• @ 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;
}
//不对的话寄刀片

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

``````
• @ 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;
}

• @ 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
for i:=1 to k do

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.

• @ 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
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.

• @ 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

• @ 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)的算法……秒杀！

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

纯水题= =、

• @ 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

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.

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

我先做的1634

结果改了两个字交上去

竟然AC了！

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

无需排序！鉴定完毕。

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

尼克的任务

• @ 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

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]

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

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

• @ 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

for i:=1 to k do

begin

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]

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

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

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

• @ 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

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啊....

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

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

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

囧...

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

ID
1577

3

(无)

1415

741

52%

3