首页 > ACM题库 > HDU-杭电 > HDU 4293-Groups-动态规划-[解题报告]HOJ
2015
05-23

HDU 4293-Groups-动态规划-[解题报告]HOJ

Groups

问题描述 :

  After the regional contest, all the ACMers are walking alone a very long avenue to the dining hall in groups. Groups can vary in size for kinds of reasons, which means, several players could walk together, forming a group.
  As the leader of the volunteers, you want to know where each player is. So you call every player on the road, and get the reply like “Well, there are Ai players in front of our group, as well as Bi players are following us.” from the ith player.
  You may assume that only N players walk in their way, and you get N information, one from each player.
  When you collected all the information, you found that you’re provided with wrong information. You would like to figure out, in the best situation, the number of people who provide correct information. By saying “the best situation” we mean as many people as possible are providing correct information.

输入:

  There’re several test cases.
  In each test case, the first line contains a single integer N (1 <= N <= 500) denoting the number of players along the avenue. The following N lines specify the players. Each of them contains two integers Ai and Bi (0 <= Ai,Bi < N) separated by single spaces.
  Please process until EOF (End Of File).

输出:

  There’re several test cases.
  In each test case, the first line contains a single integer N (1 <= N <= 500) denoting the number of players along the avenue. The following N lines specify the players. Each of them contains two integers Ai and Bi (0 <= Ai,Bi < N) separated by single spaces.
  Please process until EOF (End Of File).

样例输入:

3
2 0
0 2
2 2
3
2 0
0 2
2 2

样例输出:

2
2
Hint
The third player must be making a mistake, since only 3 plays exist.

/*
分析:
    dp,转化为区间求解。

                              2013-07-29
*/

#include"iostream"
#include"cstdio"
#include"cstring"
using namespace std;
const int N=506;

int n,dp[N],map[N][N];
inline int max(int a,int b){
    return a>b?a:b;
}
int main()
{
    int i,l;
    int a,b,ans;
    while(scanf("%d",&n)!=-1)
    {
        memset(map,0,sizeof(map));
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            if(a+b>=n)    continue;
            map[a+1][n-b]+=(n-a-b)>map[a+1][n-b]?1:0;
        }
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
        for(l=1;l<=i;l++)
            dp[i]=max(dp[i],dp[l-1]+map[l][i]);
        cout<<dp[n]<<endl;
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ice_crazy/article/details/9617209