本文主要是介绍hdu 4293 Groups，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有 n 个人，可任意分成若干组，然后每个人各提供一个信息，表示他们组前面有多少个人，后面有多少个人。问最多有多少个信息是不冲突的。
可以用DP，也可以转化成求最长路。
DP，设这n个人的编号是从1到n，则每个的提供的信息可以转化成一段区间[a+1,n-b]。那么问题就可以转化成有最多有多少个区间是互不相交的。将区间按终点排序后跑DP。dp[i]=max(dp[j]+num[i]) (0<=j<i)。其中num[j]表示这个区间i出现的次数。
最长路，同样是转化成区间[a+1,n-b]。当区间i的终点小于区间j的终点的时候，建立一条边（i,j）权值可以是区间i的出现次数，或区间j的出现次数。创建超级源点和超级汇点，跑一次最长路。
DP：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=505;
int dp[N],cnt[N][N],tot;
struct Edge
{int st,ed;Edge(){}Edge(int a,int b){st=a;ed=b;}bool operator<(const Edge &b)const{return (ed<b.ed)||(ed==b.ed&&st<b.st);}
}edge[N*N];
int main()
{int n;while(scanf("%d",&n)!=EOF){tot=0;memset(dp,0,sizeof(dp));memset(cnt,0,sizeof(cnt));for(int i=0;i<n;i++){int a,b;scanf("%d%d",&a,&b);if(a+b>=n) continue;int &tmp=cnt[a+1][n-b],x=a+1,y=n-b;if(tmp==0) edge[tot++]=Edge(x,y);cnt[x][y]=min(cnt[x][y]+1,n-a-b);}sort(edge,edge+tot);int st=edge[0].st,ed=edge[0].ed;dp[0]=cnt[st][ed];for(int i=1;i<tot;i++){st=edge[i].st,ed=edge[i].ed;dp[i]=cnt[st][ed];for(int j=i-1;j>=0;j--){if(st>edge[j].ed){dp[i]=max(dp[i],dp[j]+cnt[st][ed]);}}}int res=0;for(int i=0;i<tot;i++) res=max(res,dp[i]);printf("%d\n",res);}return 0;
}#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N=505;
int adj[N][N],valu[N],head[N],tot;
struct Edge
{int u,v,cost,pre;Edge(){}Edge(int a,int b,int c,int d){u=a;v=b;cost=c;pre=d;}
}edge[N*N];
void addEdge(int u,int v,int cost)
{edge[tot]=Edge(u,v,cost,head[u]);head[u]=tot++;
}
int spfa(int st,int ed)
{int dis[N];bool vis[N];queue<int> que;memset(dis,-1,sizeof(dis));memset(vis,0,sizeof(vis));que.push(st); vis[st]=1; dis[st]=0;while(!que.empty()){int u=que.front();que.pop();vis[u]=0;for(int i=head[u];i!=-1;i=edge[i].pre){int v=edge[i].v,cost=edge[i].cost;if(dis[v]<dis[u]+cost){dis[v]=dis[u]+cost;if(!vis[v]){vis[v]=1;que.push(v);}}}}return dis[ed];
}
int main()
{int n;while(scanf("%d",&n)!=EOF){tot=0;int sc=0,st[N],ed[N];memset(adj,0,sizeof(adj));memset(head,-1,sizeof(head));memset(valu,0,sizeof(valu));for(int i=0;i<n;i++){int a,b;scanf("%d%d",&a,&b);if(a+b>=n) continue;int x=a+1,y=n-b;int &tmp=adj[x][y];if(tmp==0) tmp=++sc;st[tmp]=x,ed[tmp]=y;valu[tmp]=min(ed[tmp]-st[tmp]+1,valu[tmp]+1);}for(int i=1;i<=sc;i++){for(int j=1;j<=sc;j++)if(ed[i]<st[j]) {addEdge(i,j,valu[i]);}addEdge(0,i,0);addEdge(i,sc+1,valu[i]);}printf("%d\n",spfa(0,sc+1));}return 0;
}
这篇关于hdu 4293 Groups的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
