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

題意：

有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,rt<<1 #define rc m + 1,r,rt<<1|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

總結

以上是生活随笔為你收集整理的hdu 4293 Groups DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。