HDU 4293---Groups(區間DP)，hdu4293---groups
題目鏈接
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 A
i players in front of our group, as well as B
i players are following us.” from the i
th 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 A
i and B
i (0 <= A
i,B
i < 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
*/
