Groups
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1966 Accepted Submission(s):
778
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.
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).
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
题意：有n个人排成一列，n个人中连续的一排人[i,j](1<=i,j<=n)可能是一组的,也可能不是.现在每个人都会说两个信息，即那个人当前所在组的前面和后面分别有多少人。已知其中有人提供的信息有误。现在要你判断n个人中最多有多少人所给的信息是正确的。
思路：区间dp,dp[i]:前i个人当中最多有多少人说对了。s[i][j]:当以区间[i,j]为一个组时，区间[i,j]内最多有多少人说对了结果。
转移方程为：dp[i]=max(dp[i],dp[j]+s[j+1][i]),即编号到i为止的人当中说对的人的个数可能是由两部分组成:编号到j为止的人当中说对的人的个数+若以[j+1,i]为一组时，该区间内说对结论的人个数。
AC代码：
#include <iostream> #include<algorithm> #include<vector> #include<cstring> #include<queue> #include<bitset> #include<cmath> using namespace std; #define N_MAX 509 #define INF 0x3f3f3f3f #define EPS 1e-6 int n; int dp[N_MAX],s[N_MAX][N_MAX];//s[i][j]:以[i,j]为一组时，这个区间里面最多有几个人说了真话 int main() { 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){//区间[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; } return 0; }