学步园

题意：有n（n<=500）个人组团去食堂，每个人说前面有x个人后面有y个人，问最多有多少个人说的是真话，且这些话是彼此不矛盾的。
题解：看这个题想应该是dp，若菜比赛的时候没想出来dp怎么搞，无奈只好yy了一个拓扑排序，开始因为没有处理好说相同话的情况wa了一次。
         具体建图方法：所有合法的话，按照x升序y降序排列，枚举i j如果两个人说的话不矛盾建边，这里需要注意的是相同的话最多出现n - x - y次，
         多余的直接删除，因为多余的一定是假话。然后拓扑排序找最长路。

         赛后看题解果然是dp，dp[i]表示站队伍时前i个人排成的队，使得最多人说话为真的个数。
         dp[i] = MAX(dp[i] , dp[j] + map[j][n-i]);map[i][j]表示说前面有i个人后面有j个人的话的个数，同时需要注意的是说相同话的人数不能超过n - i - j。

Sure原创，转载请注明出处。
拓扑排序版

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#include <queue>
#define MIN(a , b) ((a) < (b) ? (a) : (b))
#define MAX(a , b) ((a) > (b) ? (a) : (b))
using namespace std;
const int maxn = 502;
struct TT
{
    int l,mid,r;
    bool operator < (const TT &other) const
    {
        if(l == other.l)
        {
            return mid < other.mid;
        }
        return l < other.l;
    }
}tell[maxn];
struct node
{
    int v;
    int next;
}edge[250002];
int head[maxn],indegree[maxn],dis[maxn];
bool vis[maxn];
queue <int> Q;
int n,top,idx;

void init()
{
    memset(head,-1,sizeof(head));
    memset(indegree,0,sizeof(indegree));
    memset(vis,false,sizeof(vis));
    memset(dis,0,sizeof(dis));
    while(!Q.empty()) Q.pop();
    idx = 0;
    return;
}

void read()
{
    int u,v;
    top = 0;
    for(int i=0;i<n;i++)
    {
        scanf("%d %d",&u,&v);
        if(u + v + 1 > n) continue;
        tell[top].l = u;
        tell[top].r = v;
        tell[top++].mid = n - u - v;
    }
    n = top;
    sort(tell , tell + n);
    return;
}

void addedge(int u,int v)
{
    edge[idx].v = v;
    edge[idx].next = head[u];
    head[u] = idx++;
    return;
}

bool check(int x,int y)
{
    if(tell[x].l == tell[y].l && tell[x].r == tell[y].r) return true;
    if(tell[x].l + tell[x].mid <= tell[y].l) return true;
    return false;
}

void make()
{
    for(int i=0;i<n;i++)
    {
        if(vis[i]) continue;
        int cnt = 1,j=i+1;
        for(;j<n;j++)
        {
            if(vis[j] == false && tell[i].l == tell[j].l && tell[i].r == tell[j].r)
            {
                cnt++;
            }
            else break;
        }
        if(cnt > tell[i].mid)
        {
            for(int k=i+tell[i].mid;k<j;k++)
            {
                vis[k] = true;
            }
        }
        for(int j=i+1;j<n;j++)
        {
            if(vis[j] == false && check(i,j))
            {
                indegree[j]++;
                addedge(i,j);
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        if(indegree[i] == 0) Q.push(i);
    }
    return;
}

void topo()
{
    while(!Q.empty())
    {
        int cur = Q.front();
        Q.pop();
        for(int i=head[cur];i != -1;i=edge[i].next)
        {
            dis[edge[i].v] = MAX(dis[edge[i].v] , dis[cur] + 1);
            if(--indegree[edge[i].v] == 0)
            {
                Q.push(edge[i].v);
            }
        }
    }
    int res = 0;
    for(int i=0;i<n;i++)
    {
        res = MAX(res , dis[i]);
    }
    printf("%d\n",res+1);
    return;
}

int main()
{
    while(~scanf("%d",&n))
    {
        init();
        read();
        make();
        topo();
    }
    return 0;
}

dp版

#include <iostream>
#include <cstdio>
#include <memory.h>
#define MAX(a , b) ((a) > (b) ? (a) : (b))
using namespace std;
const int maxn = 502;
int map[maxn][maxn],dp[maxn];
int n;

void read()
{
    memset(map,0,sizeof(map));
    memset(dp,0,sizeof(dp));
    int u,v;
    for(int i=0;i<n;i++)
    {
        scanf("%d %d",&u,&v);
        if(u + v < n)
        {
            map[u][v]++;
            if(map[u][v] > n - u - v)
            {
                map[u][v] = n - u - v;
            }
        }
    }
    return;
}

void solve()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<i;j++)
        {
            int tmp = dp[j] + map[j][n-i];
            dp[i] = MAX(dp[i] , tmp);
        }
    }
    printf("%d\n",dp[n]);
    return;
}

int main()
{
    while(~scanf("%d",&n))
    {
        read();
        solve();
    }
    return 0;
}