//何老板翻译
问题描述
何老板的公司生产了一种机器人，可以用于在运动会后清理运动场上的垃圾。在机器人开始工作前，给出了一张网格状的地图，每个包含垃圾的格子都被标记上了“G”。所有的机器人一开始都位于西北方的那一角，在工作结束时所有的机器人都会走到东南方的那一角。每个机器人只能往东和往南两个方向行走。一走到有垃圾的格子，机器人就会把垃圾清理掉。一旦机器人走到了东南方那一个角，它就会自动切断电源，不能再次工作。
你的任务是计算出最少需要多少个机器人，就能清理完所有的垃圾。
例如下图：所有的机器人一开始在(1,1)位置，结束时在(6,7)位置
下图展示了两种可能的方案，其中第二种方案更好，因为它只用了两个机器人。
输入格式
由一行或多行构成，每行两个空格间隔的整数，表示一个包含垃圾的格子坐标
输入由0 0 作为结束。
注：每组测试数据的格子坐标是按行由小到大的顺序给出。
地图的行数和列数都不超过24
输出格式
若干行，每行一个整数，表示对应测试数据的结果。
样例输入
1 2
1 4
2 4
2 6
4 4
4 7
6 6
0 0
样例输出
2
题解
思路1：DP
此问题可转化为求“最长上升子序列”。
显然，假如其中的一些垃圾从左下往右上排列，其中任何两格垃圾都不能用一个机器人收集。所以，所需机器人数即为最长的这样的序列的长度（显然，其它垃圾都可以用清理这些格子的机器人清理，否则序列还可加长）。
推出方程，可用前缀和优化。
思路2：二分图
开始我们假设每个格子都需要一个机器人。
显然，如果一个机器人能从i 号垃圾走到j 号垃圾，那么j 号的机器人可以不用。
并且，每个机器人清理完某个垃圾后，接下来只能去另一格，每个垃圾又只能由一个机器人清理。这就转化为了二分图模型（如果i 号垃圾可到达j 号垃圾，则从 i 向 j’连边）。
但这种方法在时空效率上显然没有DP优秀。。。
代码
1、DP
#include <cstdio>
#include <iostream>
using namespace std;
int f[29][29],a[29][29];
int main()
{
int i,j;
while(true)
{
scanf("%d%d",&i,&j);
if((!i)&&(!j))break;
a[i][j]=1;
}
for(i=24;i;--i)
for(j=1;j<=24;j++)
f[i][j]=max(f[i+1][j],max(f[i][j-1],a[i][j]+f[i+1][j-1]));
printf("%d",f[1][24]);
return 0;
}2、二分图
#include <cstdio>
#include <iostream>
using namespace std;
const int Q=1e3;
int link[Q],ch[Q],e[Q*Q],nn[Q*Q],last[Q],x[Q],y[Q],tot=0;
bool search(int x,int k)
{for(int t=last[x];t;t=nn[t]){int y=e[t];if(ch[y]==k)continue;ch[y]=k;if((!link[y])||search(link[y],k)){link[y]=x;return true;}}return false;
}
void add(int x,int y)
{e[++tot]=y;nn[tot]=last[x];last[x]=tot;
}
int main()
{int i,j,n=0,ans=0;while(true){scanf("%d%d",&x[n+1],&y[n+1]);if((!x[n+1])&&(!y[n+1]))break;++n;}for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i!=j&&x[i]<=x[j]&&y[i]<=y[j])add(i,j);for(i=1;i<=n;i++)if(search(i,i))ans++;printf("%d",n-ans);return 0;
}
