cogs1805 飞扬的小鸟 dp

78 阅读 0 评论 52 点赞

我是靠谱客的博主鲜艳画板，最近开发中收集的这篇文章主要介绍cogs1805 飞扬的小鸟 dp，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

填坑$ing$……链接：http://cogs.pro/cogs/problem/problem.php?pid=1805

题意：一堆管子，问怎么用最少点击次数穿出去。

就是个裸背包啊……优化都没有……

另外这份代码在$UOJ$上被$Hack$了，有没有某位$dalao$帮忙找找问题……

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 using namespace std;
 6 const int maxn=10000+5,maxm=1000+5,inf=0x3f3f3f3f;
 7 int x[maxn],lowe[maxn],uppe[maxn],y[maxn],cnt[maxn][maxm],n,m,k;
 8 int haha()
 9 {
10
freopen("birda.in","r",stdin);
11
freopen("birda.out","w",stdout);
12
scanf("%d%d%d",&n,&m,&k);uppe[0]=m+1;
13
for(int i=0;i<n;i++)scanf("%d%d",&x[i],&y[i]),uppe[i+1]=m+1;
14
for(int i=1;i<=k;i++)
15 
{
16
int x;scanf("%d",&x);
17
scanf("%d%d",&lowe[x],&uppe[x]);
18 
}
19
cnt[0][0]=inf;
20
int done=0;
21
int minn=inf;bool ok=0;
22
for(int i=1;i<=n;i++)
23 
{
24
ok=0;
25
for(int j=0;j<=m;j++)cnt[i][j]=inf;
26
for(int j=1;j<uppe[i];j++)
27 
{
28
minn=inf;
29
if(j-x[i-1]>lowe[i-1])
30 
{
31
minn=min(minn,cnt[i-1][j-x[i-1]]+1);
32
minn=min(cnt[i][j-x[i-1]]+1,minn);
33 
}
34
if(minn<inf)cnt[i][j]=minn,ok=1;
35 
}
36
for(int j=lowe[i]+1;j<uppe[i];j++)
37
if(j+y[i-1]<uppe[i-1]&&cnt[i-1][j+y[i-1]]<cnt[i][j])cnt[i][j]=cnt[i-1][j+y[i-1]],ok=1;
38
for(int j=0;j<=lowe[i];j++)cnt[i][j]=inf;
39
if(uppe[i]>m)
40 
{
41
for(int j=uppe[i]-x[i-1];j<uppe[i];j++)
42 
{
43
cnt[i][m]=min(cnt[i][m],cnt[i-1][j]+1);
44
cnt[i][m]=min(cnt[i][m],cnt[i][j]+1);
45 
}
46
if(cnt[i][m]<inf)ok=1;
47 
}
48
if(!ok)
49 
{
50
printf("0n%dn",done);
51
return 0;
52 
}
53
if(uppe[i]!=m+1)done++;
54 
}
55
minn=inf;
56
for(int i=lowe[n]+1;i<uppe[n];i++)minn=min(minn,cnt[n][i]);
57
printf("1n%dn",minn);
58 }
59 int sb=haha();
60 int main(){;}