? ? ? ?模型挺好的dp題，其實這道題就是建一個模型然后就很容易想到遞推過程了，我們可以把每個人的描述，存到數(shù)組a中，a[l][r]表示左邊有l(wèi)個，到第r個這個人所在一層停止。。。然后就可以寫出轉移狀態(tài)方程了。注意如果dp[i]>dp[j] && i < j ?則需要把dp[j]更新為dp[i]。

?

    #include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define CLR(a, b) memset(a, b, sizeof(a))



using namespace std;



const int N = 555;



int a[N][N], dp[N];



int main()

{

    //freopen("input.txt", "r", stdin);

    int n, i, j, l, r;

    while(scanf("%d", &n) != EOF)

    {

        CLR(a, 0);

        CLR(dp, 0);

        for(i = 0; i < n; i ++)

        {

            scanf("%d%d", &l, &r);

            a[l][n - r] ++;

        }

        for(i = 0; i < n; i ++)

        {

            for(j = n - i - 1; j >= 0; j --)

            {

                dp[n - j] = max(dp[n - j], dp[i] + min(n - j - i, a[i][n - j]));

                dp[n - j] = max(dp[n - j], dp[n - j - 1]);

            }

        }

        printf("%d\n", dp[n]);

    }

}


  

?

?

HDU 4293 Groups