【luogu1941】【noip2014】 飞扬的小鸟

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define rg register
 4 #define ll long long
 5 const int N=10000+5,M=1000+5,inf=1e9+7;
 6 int n,m,k,up[N],dw[N],f[N][M<<1],w[N];
 7 template<class t>void rd(t &x)
 8 {
 9     x=0;int w=0;char ch=0;
10     while(!isdigit(ch)) w|=ch==‘-‘,ch=getchar();
11     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
12     x=w?-x:x;
13 }
14   
15 struct wal
16 {
17     int l,h;
18 }wl[N];//下面的高度 上面的高度 
19 
20 int main()
21 {
22     for(rg int i=0;i<=n;++i)
23     for(rg int j=0;j<=m;++j) f[i][j]=inf;
24     rd(n),rd(m),rd(k);
25     memset(w,0,sizeof(w));
26     for(int i=0;i<=n;++i) wl[i].l=0,wl[i].h=m+1;
27     for(rg int i=0;i<n;++i) rd(up[i]),rd(dw[i]);
28     int x;for(rg int i=1;i<=k;++i) rd(x),rd(wl[x].l),rd(wl[x].h),w[x]=1;
29     for(rg int i=1;i<=m;++i) f[0][i]=0;//初始fa
30     for(rg int i=1;i<=n;++i)
31     {
32         for(rg int j=up[i-1]+1;j<=m+up[i-1];++j) f[i][j]=min(f[i-1][j-up[i-1]]+1,f[i][j-up[i-1]]+1);
33         for(rg int j=m;j<=m+up[i-1];++j) f[i][m]=min(f[i][j],f[i][m]);//天fa板
34         for(rg int j=1;j<=m-dw[i-1];++j) f[i][j]=min(f[i][j],f[i-1][j+dw[i-1]]);//不跳
35         for(rg int j=1;j<=wl[i].l;++j) f[i][j]=inf;
36         for(rg int j=wl[i].h;j<=m;++j) f[i][j]=inf;
37     }
38     int ans=inf;
39     for(rg int i=1;i<=m;++i) ans=min(ans,f[n][i]);
40     if(ans<inf) printf("1\n%d",ans);
41     else
42     {
43         int i,j,cnt=0;
44         for(i=n;i>=0;--i)
45         {
46             for(j=1;j<=m;++j) if(f[i][j]<inf) break;
47             if(j<=m) break;
48         }
49         for(j=0;j<=i;++j) cnt+=w[j];
50         printf("0\n%d",cnt);
51     }
52     return 0;
53 }

 1 /*
 2 10 10 6
 3 3 9
 4 9 9
 5 1 2
 6 1 3
 7 1 2
 8 1 1
 9 2 1
10 2 1
11 1 6
12 2 2
13 1 2 7
14 5 1 5
15 6 3 5
16 7 5 8
17 8 7 9
18 9 1 3
19 */
20 #include<bits/stdc++.h>
21 using namespace std;
22 #define rg register
23 #define ll long long
24 const int N=10000+5,M=1000+5,p=10007;
25 int n,m,k,up[N],dw[N],ans=N,dao=0,cnt=0;
26 template<class t>void rd(t &x)
27 {
28     x=0;int w=0;char ch=0;
29     while(!isdigit(ch)) w|=ch==‘-‘,ch=getchar();
30     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
31     x=w?-x:x;
32 }
33   
34 struct wal
35 {
36     int x,l,h;
37 }wl[N];//横坐标 下面的高度 上面的高度 
38 bool cmp(wal a,wal b){return a.x<b.x;}
39 void dfs(int x,int h,int c,int cw)
40 {
41     cnt=max(cnt,cw);
42     if(h>=m) h=m;if(h<=0) return;
43     if(c>ans) return;
44     if(x==n) {if(ans>c) ans=c;dao=1;return;}
45     int w,ww=0,cs=1+(n-h)/up[x];
46     for(rg int i=1;i<=k;++i)
47     {
48         if(wl[i].x==x) {w=i,ww=1;break;}
49         if(wl[i].x>x) break;
50     }
51     if(ww&&(h<=wl[w].l||h>=wl[w].h)) return;
52     if(ww&&(h>wl[w].l&&h<wl[w].h)) ++cw;
53     dfs(x+1,h-dw[x],c,cw);//不tiao
54     for(rg int i=1;i<=cs;++i)
55     dfs(x+1,h+i*up[x],c+i,cw);//跳 
56 }
57   
58 int main()
59 {
60     rd(n),rd(m),rd(k);
61     for(rg int i=0;i<n;++i) rd(up[i]),rd(dw[i]);
62     for(rg int i=1;i<=k;++i) rd(wl[i].x),rd(wl[i].l),rd(wl[i].h);
63     sort(wl+1,wl+k+1,cmp);
64     for(rg int i=1;i<=m;++i) dfs(0,i,0,0);
65     if(!dao) printf("0\n%d",cnt);
66     else {printf("1\n%d",ans);}
67     return 0;
68 }