HDU 4293---Groups(区间DP)

2018-06-17 23:49:14来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目链接

http://acm.split.hdu.edu.cn/showproblem.php?pid=4293

 

Problem Description
  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.
 
Input
  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).
 
Output
  For each test case your program should output a single integer M, the maximum number of players providing correct information.
 
Sample Input
3
2 0
0 2
2 2
3
2 0
0 2
2 2
 
Sample Output
2
2
Hint
The third player must be making a mistake, since only 3 plays exist.
 
Source
2012 ACM/ICPC Asia Regional Chengdu Online
 
Recommend
liuyiding   |   We have carefully selected several similar problems for you:  4288 4296 4295 4294 4292
 
题意:有n个人走在路上,这些人是分群走的,几个人几个人在一起走,现在对这n个人进行询问,每个人回答在他所在群的前面有多少人,在这个群后面有多少人,求有多少人说了真话(尽可能多的使说真话的人数多)?
 
思路:区间DP,定义dp[i] 表示前i个人中最多有多少人说了真话,s[i][j] 表示第i到第j个人为一群时,i到j最多有多少人说了真话,状态转移方程:dp[i]=dp[j]+dp[j+1][i];
 
代码如下:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
int dp[505];      ///表示i之前说真话的最多人数;
int s[505][505];  ///表示i到j为一组,组内的人数;

int main()
{
  int N;
  while(scanf("%d",&N)!=EOF)
  {
      memset(dp,0,sizeof(dp));
      memset(s,0,sizeof(s));
      for(int i=0;i<N;i++)
      {
          int x,y;
          scanf("%d%d",&x,&y);
          if(x+y<N&&s[x+1][N-y]<N-x-y)
            s[x+1][N-y]++;
      }
      for(int i=1;i<=N;i++)
      {
          for(int j=0;j<i;j++)
          {
              dp[i]=max(dp[i],dp[j]+s[j+1][i]);
          }
      }
      cout<<dp[N]<<endl;
  }
}
/*
3
2 0
0 2
2 2
*/

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:【noi 2.5_7834】分成互质组(dfs)

下一篇:2015-2016 ACM-ICPC Nordic Collegiate Programming Contest ---