交通信用网站建设,传奇网站如何建设,广州开发app哪家公司好,cm域名做网站http://acm.hdu.edu.cn/showproblem.php?pid4293 题意#xff1a; 有n个人分成了若干组走在一条林荫道路上#xff0c;导游为了能够确定人数#xff0c;要求每个人喊出自己所在的队伍前边有多少人Ai表示,后边有多少人Bi表示#xff0c;于是我们得到了n条信息。这里面有错误…http://acm.hdu.edu.cn/showproblem.php?pid4293 题意 有n个人分成了若干组走在一条林荫道路上导游为了能够确定人数要求每个人喊出自己所在的队伍前边有多少人Ai表示,后边有多少人Bi表示于是我们得到了n条信息。这里面有错误的信息也有正确的信息要求我们尽量使正确信息最大求出正确信息的数量。 思路 想了很久一直在捉摸它的最有子结构从何而来,怎样dp....今天下午虎哥给了点提示终于明白了如何做了。。。YM虎哥..... 首先我们根据每个人提供的前边Ai个人后边Bi个人可以确定这个人所在队伍的人数的范围。于是我们得到了N个区间我只要求出不想交区间最多就好了。如果区间相交的话就不能确定该队伍了。还有就是要预处理区间相同也即在同一个队伍的人数不能超过区间的值。 View Code #include iostream
#include cstdio
#include cstring
#include algorithm
#include cmath
#include queue
#include stack
#include set
#include map
#include string#define CL(a,num) memset((a),(num),sizeof(a))
#define iabs(x) ((x) 0 ? (x) : -(x))
#define Min(a,b) (a) (b)? (b):(a)
#define Max(a,b) (a) (b)? (a):(b)#define ll __int64
#define inf 0x7f7f7f7f
#define MOD 100000007
#define lc l,m,rt1
#define rc m 1,r,rt1|1
#define pi acos(-1.0)
#define test puts(-------------------)
#define maxn 10000007
#define M 100007
#define N 507
using namespace std;
//freopen(din.txt,r,stdin);struct node{int l,r;int len;int num;
}seg[N];
int dp[N];
int n,length;int cmp(node a,node b){return a.l b.l;
}
void insert(int l,int r){int i;for (i 0; i length; i){if (seg[i].l l seg[i].r r){//如果已经存在并且还没有达到区间值就可添加if (seg[i].num seg[i].len) seg[i].num;break;}}if (i length){seg[length].l l;seg[length].r r;seg[length].len r - l 1;seg[length].num 1;length;}
}
bool isok(int i,int j){//printf(****%d %d %d %d\n,i,j,seg[i].r,seg[j].l);if (seg[i].l seg[j].r) return false;//判断区间是否相交else return true;
}
void solve(){int i,j;CL(dp,0);dp[0] seg[0].num;//dp求值for (i 1; i length; i){for (j 0; j i; j){if (isok(i,j)){//puts(DDD);dp[i] max(dp[i],dp[j] seg[i].num);}}if (dp[i] 0){dp[i] seg[i].num;}}
}
int main(){//freopen(din.txt,r,stdin);int i;int Ai,Bi;while (~scanf(%d,n)){length 0;for (i 0; i n; i){scanf(%d%d,Ai,Bi);int R n - Ai;int L Bi 1;if (L R) continue;//这样的肯定不满足insert(L,R);//查看区间}sort(seg,seg length,cmp);//for (i 0; i length; i) printf(%d %d %d %d\n,seg[i].l,seg[i].r,seg[i].len,seg[i].num);solve();int MAX -inf;for (i 0; i length; i){// printf(%d\n,dp[i]);MAX max(MAX,dp[i]);}printf(%d\n,MAX);}return 0;
} 转载于:https://www.cnblogs.com/E-star/archive/2012/09/18/2691026.html
