现在的位置: 首页 > 综合 > 正文

HDU 4293 Groups(12年成都网络赛-F题-DP)

2018年04月04日 ⁄ 综合 ⁄ 共 1052字 ⁄ 字号 评论关闭

题目链接: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 ] 即为解。

#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;
}

抱歉!评论已关闭.