1203. Scientific Conference 解题报告 URAL
1203. Scientific Conference 解题报告
给多n个会议的开始结束时间，问一个人最多能参加多少会议！ 并且两个会议的时间必须至少间隔一分钟！
1<=n<=10W 1 ≤ Ts < Te ≤ 30000
又是DP，这里DP貌似做过，还是用背包思想做的，但是很明显要超时，但是看到题目类型，明显是要用的DP，怎么办呢？ O(nm)超时，就用O(n)或者O(m)吧 我最开始用的是枚举会议种类数，前提是先按照结束时间排序，而且结束时间我已经++了，所以以后就不用管间隔1的问题了！
for() dp[nod[i].t2]=max(dp[nod[i].t1]+1,dp[nod[i].t2]);//但是很明显这样dp会出现很多空缺！ 怎么办额？！ 我想过用临时数据记录上一个，然后判断这一个如果不满足某种情况下就把当前更新为上一个的内容！但是这样也有BUG…… 于是没办法我就用最笨的办法更新漏洞，加了一个for，但是有可能超时，幸运的事没有超时！ 于是胡糊里糊涂的就A掉了！
后来看人家结题报告才明白，不要枚举种类数，这样会导致dp里面有空缺，那就怎么办呢？ 枚举时间，这样就没有空缺了，但是需要将种类数转化成时间数组，就是记录cnt[j]以j为结束时间的时间，最晚开始时间是多少……
不过我认为最好的办法还是利用背包的思想，不过这里超时，背包思想帮助我理解了这个题！
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 100010
int n,m,k;
int dp[30010];
struct Node
{
int t1,t2;
}nod[MAX];
bool cmp(Node n1,Node n2)
{
return n1.t2<n2.t2;
}
int ans;
int main()
{
memset(dp,0,sizeof(dp));
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d%d",&nod[i].t1,&nod[i].t2);
nod[i].t2++;
}
sort(nod+1,nod+n+1,cmp);
for(int i=1;i<n;++i)
{///枚举的是种类
dp[nod[i].t2]=max(dp[nod[i].t1]+1,dp[nod[i].t2]);
for(int j=nod[i].t2;j<=nod[i+1].t2;++j)
{///这个for能够将中间空缺的dp补全； 或者还有一种方法就是枚举时间而非种类，但是必须将种类数组转化成时间数组
dp[j]=dp[nod[i].t2];
}
/// if(dp[nod[i].t2]==1)dp[nod[i].t2]+=cnt;
/// cnt=dp[nod[i].t2];
}
dp[nod[n].t2]=max(dp[nod[n].t1]+1,dp[nod[n].t2]);
printf("%d\n",dp[nod[n].t2]);///
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 100010
int n,m,k;
int dp[30010];
struct Node
{
int t1,t2;
}nod[MAX];
bool cmp(Node n1,Node n2)
{
return n1.t2<n2.t2;
}
int ans;
int main()
{
memset(dp,0,sizeof(dp));
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d%d",&nod[i].t1,&nod[i].t2);
nod[i].t2++;
}
sort(nod+1,nod+n+1,cmp);
for(int i=1;i<n;++i)
{///枚举的是种类
dp[nod[i].t2]=max(dp[nod[i].t1]+1,dp[nod[i].t2]);
for(int j=nod[i].t2;j<=nod[i+1].t2;++j)
{///这个for能够将中间空缺的dp补全； 或者还有一种方法就是枚举时间而非种类，但是必须将种类数组转化成时间数组
dp[j]=dp[nod[i].t2];
}
/// if(dp[nod[i].t2]==1)dp[nod[i].t2]+=cnt;
/// cnt=dp[nod[i].t2];
}
dp[nod[n].t2]=max(dp[nod[n].t1]+1,dp[nod[n].t2]);
printf("%d\n",dp[nod[n].t2]);///
return 0;
}
百度别人的代码：
[cpp]
//Ural 1203 动态规划DP 给定N个区间，求最大的不相交的区间数
//递推公式：f[i] = max(f[i-1],f[g[i]-1]+1);
#include<cstdio>
#include<string.h>
#include<utility>
#include<algorithm>
using namespace std;
const int M1 = 111111;
typedef pair<int,int> pil;
int N;
int mxp;
int f[M1];//f[i]表示时间0~i最多所能听的报告数
int g[M1];//g[i]表示以时间i结束的报告中，最晚的开始时间
pil rpt[M1];
int main()
{
scanf("%d",&N);
for(int i=0;i!=N;++i)
scanf("%d%d",&rpt[i].second,&rpt[i].first);
mxp = 0;
memset(g,-1,sizeof(g));
sort(rpt,rpt+N);
for(int i=0;i!=N;++i)
{ if(i==N-1 || rpt[i].first!=rpt[i+1].first)
g[rpt[i].first] = rpt[i].second;
mxp = max(mxp,rpt[i].first);
}
f[0] = 0;
for(int i=1;i<=mxp;++i)///枚举时间
{ if(g[i]!=-1)
f[i] = max(f[i-1],f[g[i]-1]+1);
else
f[i] = f[i-1];
}
printf("%d\n",f[mxp]);
return 0;
}
补充：软件开发 , C++ ,
