2298: [HAOI2011]problem a

Time Limit:?10 Sec??Memory Limit:?256 MB
Submit:?1326??Solved:?637

Description

一次考試共有n個人參加，第i個人說：“有ai個人分數比我高，bi個人分數比我低。”問最少有幾個人沒有說真話(可能有相同的分數)

Input

第一行一個整數n，接下來n行每行兩個整數，第i+1行的兩個整數分別代表ai、bi

Output

一個整數，表示最少有幾個人說謊

Sample Input

3

2 0

0 2

2 2

Sample Output

1

HINT

100%的數據滿足： 1≤n≤100000?? 0≤ai、bi≤n

Source

?

?

?

【分析】

　　啊。。主要是這么搞笑的題目我錯了2次。。。【還要對拍。。。

　　題目可以弄成n個區間，意思是這n個區間的分數要一樣的。

　　顯然區間不能相交但是可以完全重合。

　　把完全重合的區間合并起來，就是一個帶權的最大不相交區間了。

　　這個直接DP。。

　　還有一個我后來錯了就是那個區間的權值不能大于那個區間的規模，要取一下min。

?

1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 #define Maxn 100010 8 9 int mymax(int x,int y) {return x>y?x:y;} 10 int mymin(int x,int y) {return x<y?x:y;} 11 12 struct node 13 { 14 int x,y,c; 15 }t[Maxn]; 16 17 bool cmp(node x,node y) {return x.y==y.y?(x.x>y.x):(x.y<y.y);} 18 19 int f[Maxn]; 20 21 int main() 22 { 23 int n; 24 scanf("%d",&n); 25 int cnt=0; 26 for(int i=1;i<=n;i++) 27 { 28 int x,y; 29 scanf("%d%d",&x,&y); 30 if(x+y>=n) continue; 31 t[++cnt].x=x+1;t[cnt].y=n-y;t[cnt].c=1; 32 } 33 sort(t+1,t+1+cnt,cmp); 34 int p=1; 35 for(int i=2;i<=cnt;i++) 36 { 37 if(t[i].x==t[p].x&&t[i].y==t[p].y) t[p].c++; 38 else t[++p]=t[i]; 39 } 40 for(int i=1;i<=p;i++) t[i].c=mymin(t[i].c,t[i].y-t[i].x+1); 41 memset(f,0,sizeof(f)); 42 f[0]=0;t[0].y=0; 43 for(int i=1;i<=p;i++) 44 { 45 if(t[i].y!=t[i-1].y||i==1) 46 { 47 for(int j=t[i-1].y+1;j<=t[i].y;j++) f[j]=mymax(f[j],f[j-1]); 48 } 49 f[t[i].y]=mymax(f[t[i].y],f[t[i].x-1]+t[i].c); 50 } 51 printf("%d\n",n-f[t[p].y]); 52 return 0; 53 } View Code

?

2017-04-05?09:55:53

轉載于:https://www.cnblogs.com/Konjakmoyu/p/6667453.html

總結

以上是生活随笔為你收集整理的【BZOJ 2298】 2298: [HAOI2011]problem a （DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

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