填坑$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("0 %d ",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("1 %d ",minn); 58 } 59 int sb=haha(); 60 int main(){;}
（卧槽第一篇写了博的dp）