网上有分类把他归为动态规划类型的题目，结果读完题才发现是道最基本的贪心题目，不过因为规模较小，完全可以水过。按照给你的数据，把数据按照右边界进行排序，然后测试在每一段范围内冲突的个数，找出所欲范围内冲突个数的最大值，即为我们所要求解的结果。需要注意的两点问题——1. 输入的时候不一定是按照从小号房间往大号房间搬的方向的，也有可能是从大号房
间搬向小号房间，不过他们造成的冲突影响是一样的，所以首先要进行比较，然后再进行范围的存储；2.走廊的范围确定,如果小范围为偶数,需要减1,如果大范围为奇数,需要加1,看图就明白了，既对于数据

10

2

1 3

4 5

输出的结果应该为20而不是10，因为3和4从图上来看其实也是冲突的，注意了这一点之后此题就好做了。


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

struct pos
{
    int le;
    int ri;
}mov[201];

bool cmp(pos a,pos b)
{
    return a.ri < b.ri;
}

int main()
{
    int t,n,i,j,smax,cmax;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i = 0;i < n;i++)
        {
            scanf("%d%d",&mov[i].le,&mov[i].ri);
            if(mov[i].le > mov[i].ri)   {int temp = mov[i].le;mov[i].le = mov[i].ri;mov[i].ri = temp;}
        }
        sort(mov,mov + n,cmp);
        smax = 0;
        for(i = 0;i < n;i++)
        {
            cmax = 0;
            for(j = i;j < n;j++)
            {
                if(mov[i].ri > mov[j].le)   cmax ++;
                else if(mov[i].ri % 2 == 1)
                    if(mov[j].le == mov[i].ri + 1)  cmax ++;
                else if(mov[i].ri % 2 == 2)
                    if(mov[j].le == mov[i].ri -1)   cmax ++;
                else    break;
            }
            if(cmax > smax) smax = cmax;
        }
        printf("%d\n",smax * 10);
    }
    return 0;
}