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;
}
