很抱歉，那么迟才给大家带来题解。我也是蒟蒻，望大神觉得我有错或是怎么样不要太介意哈~

为大家分析下题目。我们可以根据数据提示可以完全的猜出题目考察的范围。

算法一：贪心，显然只能拿10-20分。不多提了。没人那么傻
算法二：单纯DFS，大概能过30%的数据。
算法三：根据题目信息进行DFS剪枝，50%的数据可以过

算法四：动态规划。很容易设计出一个时间复杂度为N^3的动规。可以拿70分。也就是枚举每一列的每个点，然后再枚举前一行所有能到这个点的点进行动规。大家手上模拟模拟相信秒懂

算法五（我自己乱想的），按题目信息建立有向图。然后spfa最短路。显然，建立图需要消耗的时间和算法四一样。但是这个思路更好理解。但是它还需要SPFA，因此可能会比算法4稍微超时。我是没试过。。

算法六：优化的动态规划。显然这道题看最后的数据范围，n^2左右的算法才能满分。那么怎么在算法四的基础上少枚举一次？？很简单。我们仔细模拟，发现他向上实质是完全背包，向下是01背包。因此只要循环2次即可，即枚举每一列的每个点即可。说专业点= =好像就是优化状态转移（其实我也听不懂233）。n（2*n）差不多。

然后按这个思路动态规划。要注意顶端的特殊情况。第一次写我没考虑，结果就拿了75，后来研究了其他人的程序才猛然醒悟，切记，切记！！！

那么我们很容易写出下面这个AC的程序

###pascal code
    program P1907;
    uses math;
    const maxn=100000001;
    var a,dp:array[-1..10000,0..1000] of longint;
        x,y:array[0..10000] of longint;
        k,m,p,l,h,i,j,ans,n,v:longint;
        ok:boolean;
        have:array[1..10000] of boolean;
    begin //main
    read(n,m,k); fillchar(a,sizeof(a),0); fillchar(dp,sizeof(dp),0); ans:=maxn;
    fillchar(have,sizeof(have),false);
    for i:=0 to n-1 do read(x[i],y[i]);
    for i:=1 to k do
    begin
     read(p,l,h); have[p]:=true;
     for j:=0 to l do a[p,j]:=maxn;
     for j:=h to m do a[p,j]:=maxn;
    end;
    for i:=0 to 1000 do a[-1,i]:=maxn;
    for i:=-1 to 10000 do a[i,0]:=maxn;
    
    for i:=-1 to 10000 do
     for j:=0 to 1000 do
      dp[i,j]:=maxn;
    
    for i:=0 to m do
     if a[0,i]<>maxn then
      dp[0,i]:=0;
    //以上是读入和初始化，注意游戏界面边缘的一些处理哦！
    for i:=1 to n do
    begin
     ok:=false; //记录是否还能继续游戏
     for j:=x[i-1]+1 to m do //向上飞的完全背包
      begin
       dp[i,j]:=min(dp[i,j],min(dp[i,j-x[i-1]]+1,dp[i-1,j-x[i-1]]+1));
       if dp[i,j]>maxn then
        dp[i,j]:=maxn;
      end;
    
     for j:=m downto m-x[i-1] do //顶部特判
      if a[i,m]<maxn then
       dp[i,m]:=min(min(dp[i,m],dp[i-1,j]+1),dp[i,j]+1);
    
     for j:=m-y[i-1] downto 1 do //向下掉
      if a[i,j]<maxn then
       dp[i,j]:=min(dp[i,j],dp[i-1,j+y[i-1]]);
    
     for j:=1 to m do //有水管的地方要改成无限大哦~
      if a[i,j]=maxn then
       dp[i,j]:=maxn;
    
     for j:=m downto 1 do
      if dp[i,j]<>maxn then
       ok:=true;
    
     if ok=false then begin v:=i; break; end; //已经无解了
    end;
    
    if ok=false then //无解的答案输出
    begin
     writeln('0'); ans:=0;
     for i:=1 to v-1 do
      if have[i]=true then
       inc(ans);
    
     writeln(ans);
     exit;
    end;
    
    for i:=m downto 1 do //计算有解时候的答案
    begin
     if dp[n,i]<ans then
      ans:=dp[n,i];
    end;
    
    writeln('1'); writeln(ans); //有解
    end.

嗯，就是酱！

#include <stdio.h>
#include <limits.h>

#define MIN(a,b) ((a)<(b)?(a):(b))

int deltaP[10001]; //向上的位移
int deltaN[10001]; //向下的位移
int upperBound[10001]; //上界
int lowerBound[10001]; //下界
int hasPipe[10001]; //该处是否存在管道
int dp[10001][1001]; //dp[i][j] = 到达 点(i,j) 的最小点击次数

int main(){
int width, height, numPipe;
int i, j, coord, answer, flag, pipeCount = 0; //pipeCount存储至多可以通过多少管道

scanf("%d %d %d", &width, &height, &numPipe);

for(i=0; i<=width; i++){
upperBound[i] = height+1; //注意：上界是开区间，即小鸟不能到达上界。
lowerBound[i] = 0; //注意：下界是开区间，即小鸟不能到达下界。
hasPipe[i] = 0;
}
for(i=1; i<=width; i++){
for(j=1; j<=height; j++)
dp[i][j] = LONG_MAX;
}
for(j=1; j<=height; j++)
dp[0][j] = 0; //横坐标为零（在屏幕左端）时点击次数为0

for(i=0; i<width; i++)
scanf("%d %d", &deltaP[i], &deltaN[i]);
for(i=0; i<numPipe; i++){
scanf("%d", &coord); //管道坐标
scanf("%d %d", &lowerBound[coord], &upperBound[coord]); //管道的处上下界
hasPipe[coord] = 1; //标记此处有管道
}

for(i=0; i<width; i++){
flag = 0;

//在 点(i,j) 处点击一次屏幕造成的状态转移（即多重背包的初始化）
for(j=lowerBound[i]+1; j<upperBound[i]; j++){
coord = MIN(j+deltaP[i], height);
if(dp[i][j] < LONG_MAX)
dp[i+1][coord] = MIN(dp[i+1][coord], dp[i][j]+1);
}

//多重背包
for(j=lowerBound[i]+1+deltaP[i]; j<=height; j++){
coord = MIN(j+deltaP[i], height);
if(dp[i+1][j] < LONG_MAX)
dp[i+1][coord] = MIN(dp[i+1][coord], dp[i+1][j]+1);
}

//不点击屏幕造成的状态转移
for(j=lowerBound[i]+1; j<upperBound[i]; j++){
if(dp[i][j] == LONG_MAX)
continue;
else
flag = 1; //若有横坐标为 i 时有可行解，则把flag置为 1，算法继续
coord = j-deltaN[i];
if(coord > 0)
dp[i+1][coord] = MIN(dp[i+1][coord], dp[i][j]);
}

if(flag){
if(hasPipe[i])
pipeCount++; //若此处有管道，计数+1
}else{
break; //flag=0，没有可行解，退出
}
}

answer = dp[width][1];
for(j=2; j<=height; j++)
answer = MIN(answer, dp[width][j]);
if(answer < LONG_MAX)
printf("1\n%d\n", answer);
else
printf("0\n%d\n", pipeCount);

return 0;
}

const maxint=1000000000;
var n,m,k,i,j,p,l,h,max,min,flag:longint;
low,high,rise,drop,tube:array[0..1000] of longint;
f:array[0..1000,0..100] of longint;

begin
readln(n,m,k);
for i:=1 to n do
begin
low[i]:=0;
high[i]:=m+1;
end;
for i:=1 to n do
readln(rise[i],drop[i]);
for i:=1 to k do
begin
readln(p,l,h);
tube[p]:=1;
low[p]:=l;
high[p]:=h;
end;
for i:=1 to n do
for j:=0 to m do
f[i,j]:=maxint;
for i:=1 to n do
begin
for j:=low[i]+1 to high[i]-1 do
begin
if j=m then
begin
for k:=1 to m-1 do
if f[i-1,k]+(j-k-1) div rise[i]+1<f[i,j] then
f[i,j]:=f[i-1,k]+(j-k-1) div rise[i]+1;
if f[i-1,j]+1<f[i,j] then
f[i,j]:=f[i-1,j]+1;
continue;
end;
if j+drop[i]<=m then
f[i,j]:=f[i-1,j+drop[i]];
for k:=1 to (j-1) div rise[i] do
if f[i-1,j-k*rise[i]]+k<f[i,j] then
f[i,j]:=f[i-1,j-k*rise[i]]+k;
end;
if tube[i]=1 then
begin
flag:=0;
for j:=low[i]+1 to high[i]-1 do
if f[i,j]<>maxint then
flag:=1;
if flag=0 then
begin
writeln(0);
writeln(max);
exit;
end
else
inc(max);
end;
end;
min:=maxlongint;
for i:=1 to m do
if f[n,i]<min then
min:=f[n,i];
writeln(1);
writeln(min);
end.
蒟蒻的70分垃圾程序...
f[i,j]表示到(i,j)点时的最少跳跃次数...
应该很好理解...

/*
这道题状态转移方程谁都可以想到不难，细节比较多，一个是本回合选择上升便不能下降，其次是管道不按顺序给，最后是一个略微的优化，就是顶部向上会停留在顶部。优化主要要求把一次摁多次的情况优化，具体看代码
*/
#include<iostream>
#include<algorithm>
using namespace std;
int X[15000],Y[15000],f[10005][1005],L[15000],H[15000],p,l,h;
bool flag=0;
int main()
{
//freopen("bird.in","r",stdin);
//freopen("bird.out","w",stdout);
int n,m,q,c;
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j]=100000;
}
}
for(int i=0;i<n;i++)
{
cin>>X[i]>>Y[i];
}
for(int i=0;i<=n;i++)
{
H[i]=m+1;
}
for(int i=1;i<=q;i++)
{
cin>>p>>l>>h;
L[p]=l;
H[p]=h;
}
c=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(j-X[i-1]>0)
{
f[i][j]=min(f[i][j],f[i-1][j-X[i-1]]+1);
f[i][j]=min(f[i][j],f[i][j-X[i-1]]+1);
}
if(j==m)
{
for(int k=j-X[i-1];k<=m;k++)
{
f[i][j] = min(f[i][j], f[i-1][k] + 1);
f[i][j] = min(f[i][j], f[i][k] + 1);
}
}
}
for(int j=m;j>0;j--)
{
if(j+Y[i-1]<=m)
f[i][j]=min(f[i][j],f[i-1][j+Y[i-1]]);
}
for(int j=1;j<=m;j++)
{
if(j<=L[i]||j>=H[i])
f[i][j]=100005;
}
if(H[i]!=m+1||L[i]!=0)
c++;
for(int k=1;k<=m;k++)
{
flag=0;
if(f[i][k]<100000)
{
flag=1;
break;
}
}
if(flag==0)
break;
}
int o=100000;
c=c-1;
for(int j=1;j<=m;j++)
{
o=min(o,f[n][j]);
}
if(o<100000)
{
cout<<1<<endl;
cout<<o<<endl;
}
else
{
cout<<0<<endl;
cout<<c<<endl;
}
//system("pause");
return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#define oo 1000000000
using namespace std;

int n,m,t,f[10001][1001];

struct node1
{
int l,h,x,y;
bool b;
}a[10001];

int main()
{
scanf("%d%d%d",&n,&m,&t);
for (int i=0;i<n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
for (int i=1;i<=n;i++)
{
a[i].l=1;
a[i].h=m;
a[i].b=0;
}
for (int i=1;i<=t;i++)
{
int p,l,h;
scanf("%d%d%d",&p,&l,&h);
a[p].l=++l;
a[p].h=--h;
a[p].b=1;
}
int ans=0;
bool suc=1;
memset(f,0,sizeof(f));
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
f[i][j]=oo;
if (j-a[i-1].x>=1)
f[i][j]=min(f[i][j],min(f[i-1][j-a[i-1].x]+1,f[i][j-a[i-1].x]+1));
}
for (int j=m-a[i-1].x;j<=m;j++)
f[i][m]=min(f[i][m],min(f[i-1][j]+1,f[i][j]+1));
for (int j=a[i].l;j<=a[i].h;j++)
if (j+a[i-1].y<=m)
f[i][j]=min(f[i][j],f[i-1][j+a[i-1].y]);
for (int j=0;j<=a[i].l-1;j++)
f[i][j]=oo;
for (int j=a[i].h+1;j<=m;j++)
f[i][j]=oo;
bool over=1;
for (int j=1;j<=m;j++)
if (f[i][j]<oo)
{
over=0;
break;
}
if (over==1)
{
printf("%d\n",0);
printf("%d\n",ans);
suc=0;
break;
}
else if (a[i].b==1)
ans++;
}
if (suc==1)
{
ans=oo;
for (int i=1;i<=m;i++)
ans=min(ans,f[n][i]);
printf("%d\n",1);
printf("%d\n",ans);
}
}

不是很懂哪里有问题。。。有没有大神帮忙看看
60分RE
```c++
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int LEN=10010,HEIGHT=1010;
const int INF=0x7fff0000;
int n,m,k;
int X[LEN],Y[LEN];
bool hasPipe[LEN];
int L[LEN],H[LEN];
int d[LEN][HEIGHT];
int dp(int x,int y);
inline int getMin(int a,int b,int c){return min((a>b?b:a),c);}
int main(){
//freopen("bird.in","r",stdin);
//freopen("bird.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<n;i++) scanf("%d%d",X+i,Y+i);
for(int i=0;i<k;i++){
int p;scanf("%d",&p);
scanf("%d%d",L+p,H+p);
hasPipe[p]=true;
}
int ans=INF;
for(int i=1;i<=m;i++) ans=min(ans,dp(n,i));
if(ans<INF){
printf("%d\n%d",1,ans);
}else{
for(int i=n;i>=0;i--)
for(int j=1;j<=m;j++)
if(dp(i,j)<INF){
int cnt=0;
//cout<<"ans:"<<ans<<endl;
for(int x=0;x<=i;x++) cnt+=hasPipe[i];
printf("%d\n%d",0,cnt);
return 0;
}
}
return 0;
}
int dp(int x,int y){
//printf("%d %d\n",x,y);
if(d[x][y]) return d[x][y];
if(hasPipe[x] && (y<=L[x] || y>=H[x])) return d[x][y]=INF;
if(y<=0 || y>m) return d[x][y]=INF;
if(x==0) return 0;
else{
if(y<m) return d[x][y]=getMin(dp(x,y-X[x-1])+1, dp(x-1,y-X[x-1])+1, dp(x-1,y+Y[x-1]));
int ans=INF;
for(int i=1;i<=X[x-1];i++)
ans=min(ans,getMin(dp(x,y-i)+1, dp(x-1,y-i)+1, dp(x-1,y+Y[x-1])));
return d[x][y]=ans;
}
}

这道题用刷表法写思路要清晰一些，不过我写得有点丑

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int INF = 1000000000;
const int maxn = 10000 + 10;
const int maxm = 1000 + 10;
int n, m, k;
int X[maxn];
int Y[maxn];
int d[maxn][2];
int pipe[maxn][2];

void update (int a, int& b) {
    if (b < 0 || a < b) b = a;
}

void init () {
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) pipe[i][1] = m+1;
    for (int i = 0; i < n; i++) scanf("%d%d", &X[i], &Y[i]);
    
    for (int i = 0; i < k; i++) {
        int p, l, h; scanf("%d%d%d", &p, &l, &h);
        pipe[p][0] = l; pipe[p][1] = h;
    }
}

int main ()
{
//  freopen("in.txt", "r", stdin);
    init();
    int cnt = 0;
    int game_over = 0;
    
    int t = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= pipe[i][0]; j++) d[j][t] = -1;
        for (int j = pipe[i][1]; j <= m+1; j++) d[j][t] = -1;
        for (int j = 0; j <= m; j++) d[j][t^1] = -1;
        
        game_over = 1;
        for (int j = pipe[i][0]+1; j < pipe[i][1]; j++) 
            if (d[j][t] >= 0) { game_over = 0; break;}
        if (game_over) { cout << "0\n" << cnt; return 0;}
        
        if(pipe[i][1] < m+1) cnt++;
        
        for (int j = 1; j <= m; j++) if (d[j][t] >= 0)
            if (j > Y[i]) update(d[j][t], d[j-Y[i]][t^1]);
            
        for (int j = 1; j <= m; j++) if (d[j][t] >= 0)
            update(d[j][t]+1, d[min(m, j+X[i])][t]);
            
        for (int j = 1; j <= m; j++) if (d[j][t] >= 0)
            update(d[j][t]+1, d[min(m, j+X[i])][t^1]);
        
        t ^= 1;
    }
    int ans = INF;
    for (int i = 1; i <= m; i++) if (d[i][t] >= 0) ans = min(ans, d[i][t]);
    cout << "1\n" << ans;
    return 0;
}

记录信息
评测状态 Accepted
题目 P1907 飞扬的小鸟
递交时间 2015-09-11 22:44:14
代码语言 C++
评测机 VijosEx
消耗时间 157 ms
消耗内存 664 KiB
评测时间 2015-09-11 22:44:15
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 660 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 660 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 664 KiB, score = 5
测试数据 #3: Accepted, time = 15 ms, mem = 664 KiB, score = 5
测试数据 #4: Accepted, time = 0 ms, mem = 660 KiB, score = 5
测试数据 #5: Accepted, time = 0 ms, mem = 660 KiB, score = 5
测试数据 #6: Accepted, time = 0 ms, mem = 664 KiB, score = 5
测试数据 #7: Accepted, time = 0 ms, mem = 660 KiB, score = 5
测试数据 #8: Accepted, time = 20 ms, mem = 664 KiB, score = 5
测试数据 #9: Accepted, time = 0 ms, mem = 660 KiB, score = 5
测试数据 #10: Accepted, time = 0 ms, mem = 660 KiB, score = 5
测试数据 #11: Accepted, time = 2 ms, mem = 660 KiB, score = 5
测试数据 #12: Accepted, time = 0 ms, mem = 660 KiB, score = 5
测试数据 #13: Accepted, time = 15 ms, mem = 664 KiB, score = 5
测试数据 #14: Accepted, time = 1 ms, mem = 660 KiB, score = 5
测试数据 #15: Accepted, time = 15 ms, mem = 660 KiB, score = 5
测试数据 #16: Accepted, time = 15 ms, mem = 664 KiB, score = 5
测试数据 #17: Accepted, time = 15 ms, mem = 660 KiB, score = 5
测试数据 #18: Accepted, time = 28 ms, mem = 664 KiB, score = 5
测试数据 #19: Accepted, time = 31 ms, mem = 660 KiB, score = 5
Accepted, time = 157 ms, mem = 664 KiB, score = 100
代码
#include <cstdio>
#include <cstring>

const int MAXN = 10005;
const int MAXM = 1005;
const int INF = 0x3f3f3f3f;

int n, m;
int X[MAXN];
int Y[MAXN];
bool pipe[MAXN];
int low[MAXN];
int high[MAXN];
int f[MAXM];
int g[MAXM];

void init()
{
int k;
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < n; ++i)
scanf("%d%d", &X[i], &Y[i]);
memset(pipe, 0, sizeof(pipe));
for (int i = 0; i < k; ++i)
{
int p, l, h;
scanf("%d%d%d", &p, &l, &h);
--p;
pipe[p] = true;
low[p] = l;
high[p] = h;
}
}

bool fail_all()
{
for (int i = 1; i <= m; ++i)
if (f[i] < INF) return false;
return true;
}

void solve()
{
for (int i = 1; i <= m; ++i) f[i] = 0;
for (int i = 0, count_pipe = 0; i < n; ++i)
{
int totmin = INF;
for (int j = 1; j <= X[i]; ++j)
{
int min = INF;
for (int k = j; k <= m; k += X[i])
{
g[k] = min;
if (f[k] < min) min = f[k];
++min;
}
if (min < totmin) totmin = min;
}
if (totmin < g[m]) g[m] = totmin;
for (int j = Y[i] + 1; j <= m; ++j)
if (f[j] < g[j - Y[i]])
g[j - Y[i]] = f[j];
memcpy(f, g, sizeof(f));
if (pipe[i])
{
for (int j = 1; j <= m; ++j)
if (!(low[i] < j && j < high[i]))
f[j] = INF;
if (fail_all())
{
printf("0\n%d\n", count_pipe);
return;
}
++count_pipe;
}
}
int min = INF;
for (int j = 1; j <= m; ++j)
if (f[j] < min) min = f[j];
printf("1\n%d\n", min);
}

int main()
{
init();
solve();

fclose(stdin); fclose(stdout);
return 0;
}

http://www.cnblogs.com/JSZX11556/p/4907703.html

70分
用了楼下的顶部特判毫无效果
呵呵，我怎么感觉nm比nm2更好想呢
1个点1个点好麻烦啊
代码如下
话说我的代码对的基本都是<3ms，而楼下都是100ms+
var
a,b:array[-200..10000,-200..1000]of longint;
f:array[-200..10000,-200..1000]of boolean;
c:array[0..10000]of boolean;
x,y,l,h:array[0..10000]of longint;
n,m,k,i,j,ans:longint;flag:boolean;
function min(a,b:longint):longint;
begin if a<b then exit(a);exit(b);end;
procedure find(x:longint);
var i,t:longint;
begin t:=0;
for i:=1 to x-1 do if c[i] then inc(t);
writeln(0);writeln(t);halt;
end;
begin
readln(n,m,k);
for i:=1 to n do read(x[i],y[i]);
for i:=1 to n do h[i]:=m;
for i:=1 to n do l[i]:=1;
for i:=1 to k do begin read(j);c[j]:=true;
read(l[j]);inc(l[j]);read(h[j]);dec(h[j]);end;
for i:=1 to m do f[0,i]:=true;
for i:=1 to n do for j:=1 to m do b[i,j]:=1000000000;
for i:=1 to n do begin flag:=false;
if not c[i] then for j:=m downto 1 do if f[i-1,j] then
begin f[i,m]:=true;b[i,m]:=min(b[i,m],b[i-1,j]+abs(m-j-1)div x[i]+1);
flag:=true;end;
for j:=l[i] to h[i] do if f[i-1,j-x[i]]or f[i,j-x[i]]
then begin f[i,j]:=true;
b[i,j]:=min(b[i,j],min(b[i,j-x[i]],b[i-1,j-x[i]])+1);
flag:=true;end;
for j:=l[i] to h[i] do if f[i-1,j+y[i]]
then begin f[i,j]:=true;b[i,j]:=min(b[i,j],b[i-1,j+y[i]]);
flag:=true;end;
if not flag then find(i);end;
ans:=maxlongint;
for i:=1 to m do if (f[n,i])and(b[n,i]<ans) then ans:=b[n,i];
writeln(1);writeln(ans);
end.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define INF 1000000000
#define MAXN 10000 + 10
using namespace std;

int u[MAXN], d[MAXN], map[MAXN][1000 + 10], f[MAXN][1000 + 10], bri[MAXN], m_d[MAXN], m_u[MAXN];

int main()
{
int n, m, k, ans = 0;
scanf("%d%d%d", &n, &m, &k);
for(int i=0; i<n; i++)
scanf("%d%d", &u[i], &d[i]);
for(int i=1; i<=n; i++)
m_d[i] = 1, m_u[i] = m;
for(int i=1; i<=k; i++){
int p, l, h;
scanf("%d%d%d", &p, &l, &h);
m_d[p] = l+1;
m_u[p] = h-1;
bri[i] = p;
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
f[i][j] = INF;
if(j > u[i-1])
f[i][j] = min(f[i][j], min(f[i-1][j-u[i-1]], f[i][j-u[i-1]])+1);
}
for(int j=m-u[i-1]; j<=m; j++)
f[i][m] = min(f[i][m], min(f[i-1][j], f[i][j])+1);
for(int j=m_d[i]; j<=m_u[i]; j++)
if(j+d[i-1] <= m)
f[i][j] = min(f[i][j], f[i-1][j+d[i-1]]);
for(int j=0; j<m_d[i]; j++)
f[i][j] = INF;
for(int j=m_u[i]+1; j<=m; j++)
f[i][j] = INF;
int flag = 1;
for(int j=1; j<=m; j++)
if(f[i][j] < INF){
flag = 0;
break;
}
if(flag){
ans = i-1;
break;
}
}
if(ans){
sort(&bri[1], &bri[1]+k);
int re = 0;
for(int i=1; i<=k; i++)
if(ans >= bri[i])
re++;
else
break;
printf("0\n%d", re);
}
else{
int re = f[n][1];
for(int i=2; i<=m; i++)
re = min(re, f[n][i]);
printf("1\n%d", re);
}
return 0;
}
DP[i][j]表示到i,j位置的最小点击屏幕数量
是一个完全背包，，，，当年考场上没看出来。。。。现在终于A了

###超详细良心题解
http://www.ofsxb.com/noip2014-day1-t3-%E9%A3%9E%E6%89%AC%E7%9A%84%E5%B0%8F%E9%B8%9F/

#include<iostream>
#include<cstdio>
#define inf 1000000000
using namespace std;
int n,m,x[10100],y[10100],up[10100],down[10100],f[10100][1100],k,h,l,p;//高m 宽n
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<n;i++)
scanf("%d%d",&x[i],&y[i]);
for(int i=1;i<=n;i++)
up[i]=m+1,down[i]=0;
for(int i=1;i<=k;i++){
scanf("%d%d%d",&p,&l,&h);
up[p]=h;down[p]=l;
}
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
f[i][j]=inf;
f[0][0]=inf;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(j-x[i-1]>=0){
f[i][j]=min(f[i][j],f[i-1][j-x[i-1]]+1);
f[i][j]=min(f[i][j],f[i][j-x[i-1]]+1);
}
if(j==m)
for(int k=j-x[i-1];k<=m;k++){
f[i][j]=min(f[i][j],f[i-1][k]+1);
f[i][j]=min(f[i][j],f[i][k]+1);
}
}
for(int j=down[i]+1;j<=up[i]-1;j++){
if(j+y[i-1]<=m)
f[i][j]=min(f[i][j],f[i-1][j+y[i-1]]);
}
for(int j=1;j<=down[i];j++)
f[i][j]=inf;
for(int j=up[i];j<=m;j++)
f[i][j]=inf;
}
int ans=inf,temp=k;
for(int i=n;i>=1;i--){
for(int j=down[i]+1;j<=up[i]-1;j++)
if(f[i][j]<inf)
ans=min(ans,f[i][j]);
if(ans!=inf) break;
if(up[i]<=m) temp--;
}
if(temp==k)
printf("1\n%d",ans);
if(temp<k)
printf("0\n%d",temp);
}

用变态规划即可

“请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。”

将解结构表示为\(\phi=(b,h,t)\)，b为1或0表示是否可以完成游戏，若可以，h表示最少点击屏幕数；否则，t表示最多可以通过多少个管道缝隙。定义\(\phi_1=(b_1,h_1,t_1)<\phi_2=(b_2,h_2,t_2)\)当且仅当\((b_1=0,b_2=1\))或\((b_1=b_2=0,t_1<t_2\))或\((b_1=b_2=1,h_1>h_2\))，则我们可以对解的表示创建全序关系，而可行解的最大值为最优解，我们可以用有符号数来优化其内存表示。

定义\(\phi+t'=\left\{\begin{array}{lr}
(b,h,t+t') & b=0\\
(b,h,t) & b=1
\end{array}\right.\)，\(\phi+h'=\left\{\begin{array}{lr}
(b,h,t) & b=0\\
(b,h+h',t) & b=1
\end{array}\right.\)

设\(\phi(x,y)\)为从(x,y)坐标开始游戏的最优解，\(\alpha(x)\)和\(\beta(x)\)分别表示上升与下降的高度，t(x)表示横坐标处是否存在管道，则对于不存在管道的平面区域$$
\phi(x,y)=\max_{h=0,1,2,...}\left\{\begin{array}{lr}
\phi(x+1,y+h*\alpha(x)) + h + t(x) & h>0 \\
\phi(x+1,y-\beta(x)) + t(x) & h=0
\end{array}\right.
$$
而所求解为\(\max_{1\le y\le m}\{\phi(0,y)\}\)。观察到表达式具有最优子结构性质，因此可以使用动态规划进行求解，时间复杂度为\(O(n*m^2)\)。

我们可以将每次可以不点击或点击多次，变为每次可以不点击、点击\(h_0\)次或原地上升一次，其中\(h_0\)为点击进入下一横坐标非管道区域的最小次数。从而可以进行下述优化，设\(\phi(x,y,\gamma)\)表示(x,y)坐标开始游戏的最优解，\(\gamma=0\)表示第一步不能为原地上升，而\(\gamma=1\)表示第一步可以为原地上升，则$$
\phi(x,y,0)=\max\left\{\begin{array}{l}
\phi(x+1,y+h_0*\alpha(x),1) + h(1) + t(x) \\
\phi(x+1,y-\beta(x),0) + t(x)
\end{array}\right.
$$$$
\phi(x,y,1)=\max\left\{\begin{array}{lr}
\phi(x+1,y+h_0*\alpha(x),1) + h(1) + t(x) \\
\phi(x+1,y-\beta(x),0) + t(x) \\
\phi(x,y+\alpha(x-1),1) + h(1) + t(x) & x\neq 0
\end{array}\right.
$$
从而得到\(O(n*m)\)的算法，空间复杂度可以实现为\(O(n+m)\)。