題目鏈接：Click here~~
題意：
有 n 個人，可任意分成若干組，然後每個人各提供一個信息，表示他們組前面有多少個人，後面有多少個人。問最多有多少個信息是不沖突的。
解題思路：
可以把 n 個人看成一段區間 [1,n]。
設每個人的信息是a、b，則這個信息代表了他們組所在的區間 S 為 [a+1,n-b]。
若某些人是一組的，當且僅當他們信息所代表的區間是相同的。
當你相信其中某一個人說的話的時候，你必定會相信另一個人所說的相同的話，於是我們可以將這些相同的區間合並到一起，記錄一下值。
問題轉化成了在 [1,n] 這段區間中分布的若干個帶有權值的區間，問如何選取一些不相交的區間，使權值之和最大。
我的做法是先按照區間的右端點進行排序，然後設 dp[ i ] 表示選取第 i 個區間時，區間 [1,S[ i ].b] 能取到的最大權值和。
則 dp[ i ] = num[ i ] + max{ dp[ j ] } （j < i 且 S[ j ].b < S[ i ].a）。
最後找到最大的 dp[ i ] 即為解。
[cpp]
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 505
struct Int
{
int a,b;
Int(){}
Int(int _a,int _b):a(_a),b(_b){}
bool operator < (const Int& s)const
{
return b < s.b || b == s.b && a < s.a;
}
}S[N];
int num[N][N],dp[N];
int main()
{
int n,a,b;
while(~scanf("%d",&n))
{
int m = 0;
memset(num,0,sizeof(num));
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
{
scanf("%d%d",&a,&b);
if(a+b > n-1 || num[a+1][n-b] == n-b-a)
continue;
if(!num[a+1][n-b])
S[m++] = Int(a+1,n-b);
++num[a+1][n-b];
}
sort(S,S+m);
int ans = 0;
for(int i=0;i<m;i++)
{
int mmax = 0;
for(int j=0;j<i;j++)
if(S[j].b < S[i].a)
mmax = max(mmax,dp[j]);
dp[i] = mmax + num[S[i].a][S[i].b];
ans = max(ans,dp[i]);
}
printf("%d\n",ans);
}
return 0;
}
